40. 组合总和 IIc

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int temp[150];
 
int cmp(const void* a,const void* b){
    int x=*(int*)a;
    int y=*(int*)b;
    if(x>y) return 1;
    return -1;
}

void dfs(int* candidates,int candidatesSize,int target,int* returnSize,int* column,int** array,int index,int count,int sum){
    if(index>candidatesSize || sum>target  ) return;
    if(index==candidatesSize && sum !=target) return;
    if(sum==target){
        printf("%d",sum);
        array[*returnSize]=(int*)malloc(sizeof(int)*count);
        column[*returnSize]=count;
        for(int i=0;i<count;i++) array[*returnSize][i]=temp[i];
        (*returnSize)++;
        return;
    }
    int use[70]={0};
    for(int i=index;i<candidatesSize;i++){
        if(use[candidates[i]]==0){
            use[candidates[i]]=1;
            temp[count]=candidates[i];
            dfs(candidates,candidatesSize,target,returnSize,column,array,i+1,count+1,sum+candidates[i]);
        }
    }
}
 
int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    qsort(candidates,candidatesSize,sizeof(int),cmp);
    *returnSize=0;
    int* column=(int*)malloc(sizeof(int)*50000);
    int** array=(int**)malloc(sizeof(int*)*50000);
    dfs(candidates,candidatesSize,target,returnSize,column,array,0,0,0);
    *returnColumnSizes=column;
    return array;
}