LeetCode 90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:
Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
解析：
此题目是在LeetCode 78 Subsets做的更新，原来题目输入的数组是无重复的，现在题目输入数组存在重复数值。
解法1:
对应于LeetCode 78中的解法1，
初始ans = [];
i=0时对应数字1，子集为[],[1]
i=1时对应数字2，子集为[],[1],[2],[1,2]
i=2时对应数字2，此时如果再在i=1步骤之前的结果做追加，则存在重复内容，只需要在i=1新产生的集合做追加。
我们用 last 来记录上一个处理的数字，然后判定当前的数字和上面的是否相同，若不同，则循环还是从0到当前子集的个数；若相同，则新子集个数减去之前循环时子集的个数当做起点来循环，这样就不会产生重复了。
具体代码如下：
[cc lang=”C++”]
class Solution {
public:
vector<vector> subsetsWithDup(vector& nums) {
vector<vector> result(1);
sort(nums.begin(), nums.end());
int size = 1, last = nums[0];
for(int i=0; i < nums.size(); i++) { if(nums[i] != last) { last = nums[i]; size = result.size(); } int new_size = result.size(); for(int j=new_size – size; j < new_size; j ++) { result.push_back(result[j]); result.back().push_back(nums[i]); } } return result; } }; [/cc] 运行结果：
解法2:
对应于LeetCode 78中的解法2，采用回溯法。
LeetCode 78中采用了一种深度优先搜索的方法，集合中的每种元素只有两种状态，要么存在要么不存在，那么在构造子集时就有选择和不选择两种情况，所以可以构造一棵二叉树，左子树表示选择该层处理的节点，右子树表示不选择，最终的叶节点就是所有子集合，树的结构如下：

在本题目里面，在处理到第二个2时，由于前面已经处理了一次2，这次我们只在添加过2的 [2] 和 [1 2] 后面添加2，其他的都不添加，那么这样构成的二叉树如下图所示：

代码只需在原有的基础上增加一句话，while (S[i] == S[i + 1]) ++i; 这句话的作用是跳过树中为X的叶节点，因为它们是重复的子集，应被抛弃。代码如下：

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> ans;
        sort(nums.begin(), nums.end());
        dfs(nums, 0, result, ans);
        return result;
    }
    void dfs(vector<int>& nums, int i, vector<vector<int>>& result, vector<int>& ans)
    {
        result.push_back(ans);
        for(int j=i; j < nums.size(); j++)
        {
            ans.push_back(nums[j]);
            dfs(nums, j+1, result, ans);
            ans.pop_back();
            while (j + 1 < nums.size() && nums[j] == nums[j + 1]) ++j;
        }
    }
};

运行结果：

参考：
https://www.cnblogs.com/grandyang/p/4310964.html