【回溯】组合总和

解题思路：回溯算法

递归结束条件：当前path中元素总和大于等于target，如果等于，复制path加入ans中

1.传入backTracing中的参数为target,index,和candidates数组以及candidates数组大小

2.若当前path中元素和大于等于target时，结束回溯

3.将当前遍历的下标传入下一次回溯的backTracking函数中

int* path;
int pathTop;
int** ans;
int ansTop;
int* length;
int getSum() {
    int i;
    int sum = 0;
    for(i = 0; i < pathTop; i++) {
        sum += path[i];
    }
    return sum;
}

void backTracking(int target, int index, int* candidates, int candidatesSize) {
    int sum;
    if((sum = getSum()) >= target) {
        //若sum等于target，将当前的组合放入ans数组中
        if(sum == target) {
            int* tempPath = (int*)malloc(sizeof(int) * pathTop);
            int j;
            for(j = 0; j < pathTop; j++) {
                tempPath[j] = path[j];
            }
            ans[ansTop] = tempPath;
            length[ansTop++] = pathTop;
        }
        return ;
    }

    int i;
    for(i = index; i < candidatesSize; i++) {
        path[pathTop++] = candidates[i];
        backTracking(target, i, candidates, candidatesSize);
        pathTop--;
    }
}

int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){
    path = (int*)malloc(sizeof(int) * 50);
    ans = (int**)malloc(sizeof(int*) * 200);
    length = (int*)malloc(sizeof(int) * 200);
    ansTop = pathTop = 0;
    backTracking(target, 0, candidates, candidatesSize);

    *returnSize = ansTop;
    *returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
    int i;
    for(i = 0; i < ansTop; i++) {
        (*returnColumnSizes)[i] = length[i];
    }
    return ans;
}

稍微简化：

int* path;
int pathTop;
int** ans;
int ansTop;
//记录每一个和等于target的path数组长度
int* length;

void backTracking(int target, int index, int* candidates, int candidatesSize, int sum) {
    //若sum>=target就应该终止遍历
    if(sum >= target) {
        //若sum等于target，将当前的组合放入ans数组中
        if(sum == target) {
            int* tempPath = (int*)malloc(sizeof(int) * pathTop);
            int j;
            for(j = 0; j < pathTop; j++) {
                tempPath[j] = path[j];
            }
            ans[ansTop] = tempPath;
            length[ansTop++] = pathTop;
        }
        return ;
    }

    int i;
    for(i = index; i < candidatesSize; i++) {
        //将当前数字大小加入sum
        sum+=candidates[i];
        path[pathTop++] = candidates[i];
        backTracking(target, i, candidates, candidatesSize, sum);
        sum-=candidates[i];
        pathTop--;
    }
}

int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){
    //初始化变量
    path = (int*)malloc(sizeof(int) * 50);
    ans = (int**)malloc(sizeof(int*) * 200);
    length = (int*)malloc(sizeof(int) * 200);
    ansTop = pathTop = 0;
    backTracking(target, 0, candidates, candidatesSize, 0);

    //设置返回的数组大小
    *returnSize = ansTop;
    *returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
    int i;
    for(i = 0; i < ansTop; i++) {
        (*returnColumnSizes)[i] = length[i];
    }
    return ans;
}