LeetCode78.子集

题目描述：78. 子集 - 力扣（LeetCode）

这道题我用的回溯，不过官方题解给的迭代法似乎更简单。

C代码如下：

int * temp;
int tempSize;
int g_numsSize;
int cnt;
 
static void backtrace(int* nums, int* returnSize, int* colcnt, int** ans, int start)
{
    if (tempSize == cnt) {
        ans[*returnSize] = (int *)malloc(sizeof(int) * cnt);
        memcpy(ans[*returnSize], temp, sizeof(int) * cnt);
        colcnt[*returnSize] = cnt;
        (*returnSize)++;
        return;
    }
    for (int i = start; i < g_numsSize; i++) {
        temp[tempSize++] = nums[i];
        backtrace(nums, returnSize, colcnt, ans, i + 1);
        tempSize--;
    }
}
 
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
    *returnSize = 0;
    int ansSize = 1 << numsSize;
    int ** ans = (int **)malloc(sizeof(int *) * ansSize);
    *returnColumnSizes = (int *)malloc(sizeof(int) * ansSize);
    temp = (int *)malloc(sizeof(int) * numsSize);
    tempSize = 0;
    g_numsSize = numsSize;
    for (cnt = 0; cnt <= numsSize; cnt++) {
        backtrace(nums, returnSize, *returnColumnSizes, ans, 0);
    }
    free(temp);
    return ans;
}