首页 > 代码库 > Subsets II

Subsets II

2024-08-03 13:39:02   219人阅读

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],  []]

 

Hide Tags
 Array Backtracking
 
与  1 相同，需考虑重复
class Solution {private:    vector<vector<int> > ret;public:    void generate(vector<int> vet,vector<int> &S,int i){        if(i==S.size()){            for(int k=0;k<ret.size();k++){                if(vet==ret[k])          //去除重复                    return;            }            ret.push_back(vet);            return;        }        generate(vet,S,i+1);        //相当于取右子树        vet.push_back(S[i]);                     generate(vet,S,i+1);       //相当于取左子树    }    vector<vector<int> > subsetsWithDup(vector<int> &S) {          sort(S.begin(),S.end());        generate(vector<int>(),S,0);        return ret;    }};

 

Subsets II


联系
我们