首页 > 代码库 > Subsets II

Subsets II

2024-07-17 20:27:08   213人阅读

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

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

 

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

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

分析：此题只要将subsets I的方法稍做修改即可。当数组中有duplicates时，在同一层的递归要避免将相同的元素放入到path中。
代码：
 1 class Solution { 2 public: 3     vector<vector<int> > subsetsWithDup(vector<int> &S) { 4         sort(S.begin(),S.end()); 5         vector<vector<int>> res; 6         vector<int> path; 7         get_subsets(S,res,path,0); 8         return res; 9     }10     void get_subsets(vector<int> &S, vector<vector<int>> & res, vector<int> & path, int start){11         res.push_back(path);12         for(int i = start; i < S.size(); i++){13             if(i != start && S[i] == S[i-1]) continue;//skip duplicates14             path.push_back(S[i]);15             get_subsets(S,res,path,i+1);16             path.pop_back();17         }18     }19 };

 


联系
我们