给定一个整数t和n个整数的集合list,将list中的数相加使其和值为t,给出所有的组合。比如t=4和n个数{4，3，2，2， 1，1}，则对应的和值为4的所有数的组合有:4，3+1,2+2,2+1+1。某个数在list中出现多少次，则该数最多可使用多少次，也可作为加数单独使用。请编写程序求解上述问题。 输入要求: 输出要求: 对于每一组测试数据，输出对应的加法表达式，每一个表达式占一行。每一个加法表达式中的加数必须按降序排列且输出结果中不能出现相同的加法表达式。如果不存在相应的加法表达式，则输出NONE。 样例输入: 4 6 4 3 2 2 1 1 5 3 2 1 1 样例输出: 4 3+1 2+2 2+1+1 NONE 实验预习: (1)写出采用回溯法求解上述问题的目标函数，约束条件以及限界函数。(2)画出采用回溯法在求解样例输入时的解空间树。 (3)画出采用回溯法求解样例输入时的搜索空间树。 (4)采用回溯法求解上述问题，写出算法的实现过程，简要分析算法的时间复杂度。 (5)编写程序求解上述问题。

#include <stdio.h>
#include <stdlib.h>

void backtrack(int *list, int n, int t, int *sum, int *count, int index, int remain, int **res, int *returnSize, int *returnColumnSizes) {
    if (remain == 0) { // 找到了一组解
        int *tmp = (int *) malloc(sizeof(int) * n);
        int j = 0;
        for (int i = 0; i < n; i++) { // 将当前使用的加数存入tmp数组中
            int cnt = count[i];
            while (cnt--) {
                tmp[j++] = list[i];
            }
        }
        res[*returnSize] = tmp; // 将tmp数组存入结果集合中
        returnColumnSizes[*returnSize] = j; // 记录当前解的长度
        (*returnSize)++; // 结果集合大小加1
        return;
    }
    if (remain < 0 || index >= n) { // 剪枝
        return;
    }
    // 当前加数单独使用
    sum[index]++; // 记录当前加数使用次数
    count[index]++; // 将当前加数使用次数加1
    backtrack(list, n, t, sum, count, index, remain - list[index], res, returnSize, returnColumnSizes); // 递归调用
    count[index]--; // 将当前加数使用次数减1
    sum[index]--;

    // 当前加数作为加数之一
    for (int i = index + 1; i < n; i++) {
        if (list[i] != list[i - 1] || sum[i - 1] > sum[i]) { // 约束条件：按降序排列且不能出现相同的加法表达式
            sum[i]++; // 将当前加数加入表达式中
            count[i]++; // 将当前加数使用次数加1
            backtrack(list, n, t, sum, count, i, remain - list[i], res, returnSize, returnColumnSizes); // 递归调用
            count[i]--; // 将当前加数使用次数减1
            sum[i]--; // 将当前加数从表达式中移除
        }
    }
}

int cmp(const void *a, const void *b) {
    return *(int *) b - *(int *) a;
}

int **combinationSum(int *candidates, int candidatesSize, int target, int *returnSize, int **returnColumnSizes) {
    qsort(candidates, candidatesSize, sizeof(int), cmp); // 对加数进行降序排序
    int **res = (int **) malloc(sizeof(int *) * 1000); // 结果集合
    int *sum = (int *) calloc(candidatesSize, sizeof(int)); // 当前表达式中每个加数的使用次数
    int *count = (int *) calloc(candidatesSize, sizeof(int)); // 每个加数已经使用的次数
    *returnSize = 0;
    backtrack(candidates, candidatesSize, target, sum, count, 0, target, res, returnSize, *returnColumnSizes);
    return res;
}

int main() {
    int target1 = 4, nums1[] = {4, 3, 2, 2, 1, 1}, size1 = 6;
    int returnSize1, *returnColumnSizes1;
    int **res1 = combinationSum(nums1, size1, target1, &returnSize1, &returnColumnSizes1);
    printf("target=%d, nums={", target1);
    for (int i = 0; i < size1; i++) {
        printf("%d", nums1[i]);
        if (i != size1 - 1) {
            printf(", ");
        }
    }
    printf("}\n");
    if (returnSize1 == 0) {
        printf("NONE\n");
    } else {
        for (int i = 0; i < returnSize1; i++) {
            int size = returnColumnSizes1[i];
            printf("%d", res1[i][0]);
            for (int j = 1; j < size; j++) {
                printf("+%d", res1[i][j]);
            }
            printf("\n");
            free(res1[i]);
        }
    }
    free(res1);
    free(returnColumnSizes1);

    int target2 = 5, nums2[] = {3, 2, 1, 1}, size2 = 4;
    int returnSize2, *returnColumnSizes2;
    int **res2 = combinationSum(nums2, size2, target2, &returnSize2, &returnColumnSizes2);
    printf("target=%d, nums={", target2);
    for (int i = 0; i < size2; i++) {
        printf("%d", nums2[i]);
        if (i != size2 - 1) {
            printf(", ");
        }
    }
    printf("}\n");
    if (returnSize2 == 0) {
        printf("NONE\n");
    } else {
        for (int i = 0; i < returnSize2; i++) {
            int size = returnColumnSizes2[i];
            printf("%d", res2[i][0]);
            for (int j = 1; j < size; j++) {
                printf("+%d", res2[i][j]);
            }
            printf("\n");
            free(res2[i]);
        }
    }
    free(res2);
    free(returnColumnSizes2);

    return 0;
}

时间复杂度分析：假设有n个加数，最坏情况下需要遍历所有可能的加法表达式，因此时间复杂度为O(2^n)。但是，由于采用了剪枝策略，因此时间复杂度会远远低于最坏情况。另外，由于需要记录每个解的长度，因此需要额外的空间来存储结果。