90. Subsets II (Medium)

Posted on | In
  1. Subsets II (Medium)

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:

1
2
3
4
5
6
7
8
9
10
Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

  1. 递归：在上一题的基础上，增加了重复的元素

    所以在判断中遇到重复元素跳过即可

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    vector<vector<int>> res;
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<int> temp;
            backtrack(nums, 0, temp);
            return res;
        }
        
        void backtrack(vector<int>&nums, int first, vector<int>& temp){
            res.push_back(temp);
            for(int i=first; i<nums.size(); i++){
                if(i==first || nums[i]!=nums[i-1]){
                    temp.push_back(nums[i]);
                    backtrack(nums, i+1, temp);
                    temp.pop_back();
                }
            }
        }

  1. 迭代

    和上一题也类似，需要除去重复的情况，依旧是判断是否是第一个或者前后两个元素是否一样。但需要注意一点，对于相同元素的情况，之前res中加过前一个元素的vector不再考虑，只考虑新加入的，所以j要在新的sz之前赋值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> res;
            res.push_back({});
            vector<int> temp;
            int sz = 0;
            for(int i=0; i<nums.size(); i++){
                int j = !i||nums[i]!=nums[i-1]?0:sz;
                sz = res.size();
                for(; j<sz; j++){
                    res.push_back(res[j]);
                    res.back().push_back(nums[i]);
                }
            }
            return res;
        }