【回溯】子集

解题思路：回溯算法

递归结束条件：如果startIndex大于数组长度，返回

1.若startIndex大于数组长度，返回

2.从startIndex开始遍历数组，每次将当前元素放入path中，将当前path复制然后进入下一层。从递归出来后将数组中元素删除

int* path;
int pathTop;
int** ans;
int ansTop;
//记录二维数组中每个一维数组的长度
int* length;
void copy() {
    int* tempPath = (int*)malloc(sizeof(int) * pathTop);
    int i;
    for(i = 0; i < pathTop; i++) {
        tempPath[i] = path[i];
    }
    ans = (int**)realloc(ans, sizeof(int*) * (ansTop+1));
    length[ansTop] = pathTop;
    ans[ansTop++] = tempPath;
}

void backTracking(int* nums, int numsSize, int startIndex) {
    if(startIndex >= numsSize) {
        return;
    }
    int j;
    for(j = startIndex; j < numsSize; j++) {
        path[pathTop++] = nums[j];
        copy();
        backTracking(nums, numsSize, j+1);
        pathTop--;
    }
}

int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    path = (int*)malloc(sizeof(int) * numsSize);
    ans = (int**)malloc(0);
    length = (int*)malloc(sizeof(int) * 5000);
    ansTop = pathTop = 0;
    backTracking(nums, numsSize, 0);
    pathTop = 0;
    copy();
    *returnSize = ansTop;
    *returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
    int i;
    for(i = 0; i < ansTop; i++) {
        (*returnColumnSizes)[i] = length[i];
    }
    return ans;
}