90. 子集 II

难度：中等

题目

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

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

Reference

题解

先统计集合中每个元素的出现次数，再根据出现次数进行回溯，最后重新生成每个集合。

/**
 * 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 *convert(int *count, int countLen, int *returnSize)
{
    int i = 0, j = 0, k = 0;
    *returnSize = 0;
    for (i = 0; i < countLen; i++)
        (*returnSize) += count[i];
    int *ret = (int *)malloc(sizeof(int) * *returnSize);
    for (i = 0; i < countLen; i++)
        for (j = 0; j < count[i]; j++)
            ret[k++] = i - 10;
    return ret;
}

void dfs(int **ret, int *retSize, int *count, int *current, int currentPos, int maxPos, int *number)
{
    if (currentPos == maxPos)
    {
        ret[*number] = convert(current, maxPos, retSize + *number);
        (*number)++;
    }
    else
    {
        if (count[currentPos] == 0)
            dfs(ret, retSize, count, current, currentPos + 1, maxPos, number);
        else
        {
            int i = 0;
            for (i = 0; i <= count[currentPos]; i++)
            {
                current[currentPos] = i;
                dfs(ret, retSize, count, current, currentPos + 1, maxPos, number);
                current[currentPos] = 0;
            }
        }
    }
}

int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    int *count = (int *)malloc(sizeof(int) * 21), *buffer = (int *)malloc(sizeof(int) * 21),
        i = 0, **ret = NULL;
    memset(count, 0, sizeof(int) * 21);
    memset(buffer, 0, sizeof(int) * 21);
    *returnSize = 1;
    for (i = 0; i < numsSize; i++)
        count[nums[i] + 10]++;
    for (i = 0; i < 21; i++)
        *returnSize *= count[i] + 1;
    *returnColumnSizes = (int *)malloc(sizeof(int) * *returnSize);
    ret = (int **)malloc(sizeof(int *) * *returnSize);
    i = 0;
    dfs(ret, *returnColumnSizes, count, buffer, 0, 21, &i);
    return ret;
}

评论