1.核心思想

dfs+回溯

3. 分析流程

方法一：
dfs中最重要的是搜索顺序，做到不重不漏！！！
至于本题搜索顺序：依次枚举每个数字出现的次数
比如1122233
1: 可以枚举的次数为0,1,2
2: 枚举的次数可以为：0,1,2,3
3: 枚举的次数可以为：0,1,2

题目描述举例

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

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

样例

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

C 代码

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

int cmp(const void* a, const void* b)
{
    int left = *(int*)a;
    int right = *(int*)b;
    if(left <= right){
        return -1;
    } else {
        return 1;
    }
}

void dfs(int* nums, int u, int L)
{
    //printf("u=%d, L=%d\n", u, L);
    if(u == L){
        col[cnt] = idx;
        memcpy(ans[cnt++], path, sizeof(int) * idx);
        /*
        for(int i = 0; i < idx; i++){
            printf("%d ", path[i]);
        }
        puts("");
        */
        return ;
    }

    //计算当前数字的个数
    int k = 0;
    while(u + k <= L - 1 && nums[u + k] == nums[u]) k++;

    //枚举每个数字选取的次数
    for(int i = 0; i <= k; i++){

        for(int j = 0; j < i; j++){
            path[idx++] = nums[u];
        }
        dfs(nums, u + k, L);

        idx -= i;
    }
}

/**
 * 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** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
//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. sort:
    qsort(nums, numsSize, sizeof(int), cmp);

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

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

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

    return ans;
}