Leetcode-90.子集II

发表于 分类于 阅读次数：

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

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets-ii

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1：回溯+剪枝

思路:78题的升级版，出现了重复子集，那么我们要先对数组排序，然后只需要在回溯过程中进行判断，若这一位与上一位相同就直接进行下一轮回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
private:
    vector<vector<int>> res;
    vector<int> temp;
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        int n=nums.size();
        sort(nums.begin(),nums.end());
        ziji(nums,n,0,0);
        return res;
    }
    void ziji(vector<int>& nums,int n,int i,int count)
    {
        
        res.push_back(temp);
        int k;
        for(k=i;k<n;k++)
        {
            if(k>i&&nums[k]==nums[k-1])
                continue;
            temp.push_back(nums[k]);
            ziji(nums,n,k+1,count+1);
            temp.pop_back();
        }
        return ;
    }
};