【贪心】组合总和2

解题思路：回溯算法

递归结束条件：path中的元素和大于等于target，若等于将path复制放入ans中

1.设置函数backTracking，传入参数为startIndex,candidates,target,sum, candidatesSize

2.若递归条件满足，返回

3.用for循环遍历到candidates最后一位，中间调用backTracking

4.若前一个数字已经有解（j>startIndex且candidates[j]==candidates[j-1]，跳过当前元素）

int* path;
 int pathTop;
 int** ans;
 int ansTop;
 //记录每个数组的长度
 int* length;
int cmp_int(const void* _a , const void* _b)
{
    int* a = (int*)_a;    //强制类型转换
    int* b = (int*)_b;
    return *a - *b;
}

void backTracking(int startIndex, int* candidates, int target, int sum, int candidatesSize) {
    if(sum >= target) {
        if(sum == target) {
            int* tempPath = (int*)malloc(sizeof(int) * pathTop);
            int i;
            for(i = 0; i < pathTop; i++) {
                tempPath[i] = path[i];
            }
            length[ansTop] = pathTop;
            ans[ansTop++] = tempPath;
        }
        return ;
    }
    int j;
    for(j = startIndex; j < candidatesSize; j++) {
        if(j > startIndex && candidates[j] == candidates[j - 1])
            continue;
        sum += candidates[j];
        path[pathTop++] = candidates[j];
        backTracking(j+1,candidates,target, sum, candidatesSize);
        sum -= candidates[j];
        pathTop--;
    }
}

int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){
    path = (int*)malloc(sizeof(int) * 50);
    ans = (int**)malloc(sizeof(int*) * 100);
    ansTop = pathTop = 0;
    length = (int*)malloc(sizeof(int) * 100);
    qsort(candidates,candidatesSize,sizeof(int),cmp_int);
    backTracking(0, candidates, target, 0, candidatesSize);

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