1.核心思想

dfs+回溯

3. 分析流程

方法一：
dfs中最重要的是搜索顺序，做到不重不漏！！！
至于本题搜索顺序：依次枚举每个位置是否选择，不选择为0，选择为1

方法二：
二进制法求解：对于长度 n的 数组，所有的集合数 2^n, 可以用0～2^n - 1数来代替， 每个数对应的二进制
位是0，代表对应的数组位置不选择，二进制位是1代表对应的数组位置选择。

题目描述举例

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

样例

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

C 代码

// 方法一： DFS
#define N 100010
int** ans;
int cnt;
int* path;
int idx;
int* col;

void dfs(int* nums, int u, int L)
{
    if(u == L){
        col[cnt] = idx;
        memcpy(ans[cnt++], path, sizeof(int) * idx);
        return ;
    }

    for(int i = 0; i <= 1; i++){
        if(i == 0){
            dfs(nums, u + 1, L);
        } else {
            path[idx++] = nums[u];
            dfs(nums, u + 1, L);
            idx --;
        }
    }
}

/**
 * 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** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    if(nums == NULL || numsSize < 0){
        *returnSize = 0;
        return NULL;
    }

    // 1.reset
    cnt = 0;
    idx = 0;

    // 2.prepare
    int total = 1;
    for(int i = 1; i <= numsSize; i++){
        total *= 2;
    }
    ans = (int**)malloc(sizeof(int*) * total);
    for(int i = 0; i < total; i++){
        ans[i] = (int*)malloc(sizeof(int) * numsSize);
    }
    path = (int*)malloc(sizeof(int) * numsSize);
    col = (int*)malloc(sizeof(int) * total);

    // 3. dfs
    dfs(nums, 0, numsSize);

    // 4. result
    *returnSize = cnt;
    *returnColumnSizes = col;

    return ans;
}

//方法二：二进制求解
/**
 * 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** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    if(nums == NULL || numsSize < 0){
        *returnSize = 0;
        return NULL;
    }

    int total = 1 << numsSize;

    int **ans = (int**)malloc(sizeof(int*) * total);
    for(int i = 0; i < total; i++){
        ans[i] = (int*)malloc(sizeof(int) * numsSize);
    }
    int * col = (int*)malloc(sizeof(int) * total);

    int cnt = 0;
    int idx = 0;
    for(int i = 0; i < total; i++){
        //int t = i;
        for(int j = 0; j <= numsSize - 1; j++){
            if(i >> j & 1){
                ans[cnt][idx++] = nums[j];
            }
        }
        col[cnt] = idx;
        cnt++;
        idx = 0;
    }

    *returnSize = cnt;
    *returnColumnSizes = col;
    return ans;
}