首页 > 代码库 > Subsets

Subsets

2024-07-19 02:21:43   219人阅读

Given a set of distinct integers, 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,3], a solution is:

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

思路：先对输入序列进行排序，然后使用DFS求解即可。

 1 class Solution { 2 public: 3     vector<vector<int>> subsets( vector<int> &S ) { 4         sort( S.begin(), S.end() ); 5         vector<int> subset; 6         DFS( subset, 0, S ); 7         return result; 8     } 9 private:10     void DFS( vector<int> &subset, size_t index, vector<int> &S ) {11         if( index == S.size() ) { result.push_back( subset ); return; }12         DFS( subset, index+1, S );13         subset.push_back( S[index] );14         DFS( subset, index+1, S );15         subset.pop_back();16         return;17     }18     vector<vector<int>> result;19 };

 

Subsets


联系
我们