题目内容

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

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

示例

示例 1：

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

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

提示

1、1 <= nums.length <= 10
2、-10 <= nums[i] <= 10

题解

与之前的lc78题不同的地方在于，本题中元素不唯一，因此无法采用二进制表示的方式求解答案。本题可以使用枚举法来求解。

首先，对于每个nums[i]，有对应Cn个。

然后，使用枚举的方式，就需要从前往后枚举每个数选多少个，然后把全部的状态枚举出来就是答案

当然，我们在枚举的时候，需要将Cn求出来，因此在实现上可以先将数组进行排序，然后保证相同的数都在一起，这样求解Cn比较容易；或者采用hash表也可以实现，这里就不再赘述了。

具体，请看代码实现。

代码

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    int n;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        //先排序，把所有相同的元素放在一起，之后统计相同元素个数，对于每个相同元素可以选择的次数为0-t(t表示元素出现次数)
        //将所有元素的所有次数可能相互组合即可得到所有解集
        sort(nums.begin(), nums.end());
        n = nums.size();
        dfs(nums, 0);
        return res;
    }

    void dfs(vector<int>& nums,int u){
        if(u == n){
            res.push_back(path);
            return;
        }

        int k = 0;  //k表示当前元素出现次数
        while(u + k < n && nums[u] == nums[u + k]) k ++;

        //i <= k是有等号的，i = 0时表示一个元素都不放，i = k时表示已经放了k个元素，i == k这个条件需要好好体会一下
        for(int i = 0; i <= k; i++){
            dfs(nums, u + k);
            path.push_back(nums[u]);
        }

        //弹出k + 1个元素，因为push了k + 1个nums[u]
        for(int i = 0; i <= k; i ++) path.pop_back();
    }
};