Problem description:

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.

1
2
3
4
5
6
7
8
9
10
11
12
Example:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Solution:
This question is very similar to 39. Combination Sum and 78. Subsets.

  1. Sort the array
  2. When recursion, we need to check for the duplicate elements, if i is equal to previous item then bypass it
  3. A major difference is that we need to use i to do the backtrack, instead of pos+1 in combination.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> tmp;
        sort(nums.begin(), nums.end());
        backtrack(res, tmp, nums, 0);
        return res;
    }
    void backtrack(vector<vector<int>>& res, vector<int>& tmp, vector<int> nums, int pos){
        res.push_back(tmp);
        for(int i = pos; i< nums.size(); i++){
            if(i > pos && nums[i] == nums[i-1]) continue;
            tmp.push_back(nums[i]);
            backtrack(res, tmp, nums, i+1); //this is the major difference, need to throw in i, instead of pos
            tmp.pop_back();
        }
    }
};