090.SubsetsII.md

tags: Array

#LeetCode 90 SubSets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Diffculty
Medium

Similar Problems
[LeetCode 78] Subsets

Analysis

Solutions

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector<vector<int>> allSets;
        vector<int> sol;
        allSets.push_back(sol);
        sort(S.begin(), S.end());
        findSubsetsWithDup(S, 0, sol, allSets);
        return allSets;
    }
    
    void findSubsetsWithDup(vector<int> &S, int start, vector<int> &sol, vector<vector<int>> &allSets) {
        for(int i=start; i<S.size(); i++) {
            if(i>start && S[i]==S[i-1]) continue;
            sol.push_back(S[i]);
            allSets.push_back(sol);
            findSubsetsWithDup(S, i+1, sol, allSets);
            sol.pop_back();
        }
    }
};

Reference