90. Subsets II.md

90. Subsets II

思路

这题就是78. Subsets的升级版，做法也和此题类似，可参考之前78. Subsets题解。 为了使相同的元素都是挨着的，我们首先需要对nums进行排序。

思路一、DFS

构造一棵二叉树，左子树表示选择该层处理的节点，右子树表示不选择，最终的叶节点就是所有子集合，以[1,2,2]为例，树的结构如下：

                        []        
                   /          \        
                  /            \     
                 /              \
              [1]                []
           /       \           /    \
          /         \         /      \        
       [1 2]       [1]       [2]     []
      /     \     /   \     /   \    / \
  [1 2 2] [1 2]  X   [1]  [2 2] [2] X  []

需要注意避免重复结果: 如果下一层对应元素满足nums[level+1] == nums[level]，若不打算访问当前层对应元素（nums[level]），那么也不应该访问下一层对应元素，所以在向右子树下降之前应该跳过重复值，详见代码。

思路二

此题也可以使用迭代的方式来完成此题。 参考78. Subsets题解，当处理到第一个2时，此时的子集合为[], [1], [2], [1, 2]， 而这时再处理第二个2时，如果在[]和[1]后直接加2会产生重复，所以只能在上一个循环生成的后两个子集合后面加2。 所以我们用last来记录上一个处理的数字，然后判定当前的数字和上面的是否相同，若不同，则循环还是从0到当前子集的个数，若相同， 则新子集个数减去之前循环时子集的个数当做起点来循环，这样就不会产生重复了。

C++

思路一

好理解版

class Solution {
private:
    void DFS(const vector<int>&nums, vector<vector<int>>&res, vector<int>&out, int level){
        if(level == nums.size()){
            res.push_back(out);
            return;
        }
        
        // 左子树
        out.push_back(nums[level]);
        DFS(nums, res, out, level+1);
        out.pop_back();
        
        // 右子树
        int i = level + 1;
        while(i < nums.size() && nums[i] == nums[level]) i++; // 避免重复, 唯一和78. Subsets不同的地方
        DFS(nums, res, out, i);
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>>res;
        vector<int>out;
        sort(nums.begin(), nums.end());
        DFS(nums, res, out, 0);
        return res;
    }
};

简洁版

class Solution {
void DFS(vector<vector<int>> &res, int level, vector<int> &subset, vector<int> &nums) {
        res.push_back(subset);
        for (int i = level; i < nums.size(); ++i) {
            subset.push_back(nums[i]);
            DFS(res, i + 1, subset, nums);
            subset.pop_back();
            while (i + 1 < nums.size() && nums[i] == nums[i + 1]) ++i;
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>>res;
        vector<int>subset;
        vector<bool>visited(nums.size(), false);
        sort(nums.begin(), nums.end());
        DFS(res, 0, subset, nums);
        return res;
    }
};

思路二

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        vector<vector<int>>res;
        res.push_back(vector<int>{});
        sort(nums.begin(), nums.end());
        int last = nums[0], size = 1;
        for(int i = 0; i < nums.size(); i++){
            if(last != nums[i]){
                last = nums[i];
                size = res.size();
            }
            int newSize = res.size();
            for (int j = newSize - size; j < newSize; ++j) {
                res.push_back(res[j]);
                res.back().push_back(nums[i]);
            }
        }
        return res;
    }
};