首页 > 代码库 > Subsets II

Subsets II

2024-07-18 15:02:35   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],  []]

思路：先对输入序列进行排序，然后使用DFS生成所有的组合。为了避免重复，在确定当前元素的选取方案之后，应该从下一个比它大的元素所在的位置递归。

 1 class Solution { 2 public: 3     vector<vector<int>> subsetsWithDup( vector<int> &S ) { 4         if( S.empty() ) { return subsets; } 5         sort( S.begin(), S.end() ); 6         vector<int> subset; 7         GenerateSub( subset, S.begin(), S.end() ); 8         return subsets; 9     }10 private:11     void GenerateSub( vector<int> subset, vector<int>::iterator begin, vector<int>::iterator end ) {12         if( begin == end ) { subsets.push_back( subset ); return; }13         auto next = upper_bound( begin, end, *begin );14         GenerateSub( subset, next, end );15         while( begin != next ) {16             subset.push_back( *begin );17             GenerateSub( subset, next, end );18             ++begin;19         }20         return;21     }22     vector<vector<int>> subsets;23 };

 


联系
我们