首页 > 代码库 > Subsets

Subsets

2024-07-02 07:25:38   224人阅读

Problem 1:

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

Problem 2:

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

分析：

问题1是经典的深度递归二分支的算法，对于容器中的元素每个都需要考虑在子集合中与不在子集合中两种情况，一共有2n种。容器中所有的元素不同，所以一定不存在相同的两个子集合，这时的枚举程序用递归非常容易写。这样的程序基本模式是顺序扫描每个元素，对每个元素，分加入当前集合（第16行）与不加入当前集合（第19-21行）两种情况进行递归考察下一个元素，直到所有元素都考察完，这时就得到了一个子集（第12-14行）。参考下面的代码。

 1 class Solution {
 2 public:
 3     vector<vector<int> > subsets(vector<int> &S) {
 4         vector<vector<int> > result;
 5         vector<int> cur;
 6         sort(S.begin(), S.end());
 7         recursiveSubsets(result, cur, S, 0);
 8         return result;
 9     }
10     
11     void recursiveSubsets(vector<vector<int> > &result, vector<int> &cur, const vector<int> &s, size_t idx) {
12         if(idx == s.size()) {
13             result.push_back(cur);
14         } else {
15             // do not add s[idx]
16             recursiveSubsets(result, cur, s, idx+1);
17             
18             // add s[idx]
19             cur.push_back(s[idx]);
20             recursiveSubsets(result, cur, s, idx+1);
21             cur.pop_back();
22         }
23     }
24 };

问题2中集合中出现了重复元素，如果还按照上述的枚举方式，那么会有一些重复的集合。例如，原始集合是[1, 2, 2]，按照上述的枚举方式，[1, 2]这个集合会被枚举两次，因为第2个元素与3个元素相同，但分别会独立的考虑两次。这里去重的思路很简单，因为原始集合开始排过顺序，所以相同的元素都是相邻的，而它们在最终的子集中出现的情况只有有限的几种，比如a元素重复了b次，那么子集中会有b+1种，而非上述枚举中的2b种。比如2重复了两次，那么子集合中只会有[], [2], [2, 2]三种情况。

 1 class Solution {
 2 public:
 3     vector<vector<int> > subsetsWithDup(vector<int> &S) {
 4         vector<vector<int> > result;
 5         vector<int> cur;
 6         sort(S.begin(), S.end());
 7         recursiveSubsets(result, cur, S, 0);
 8         return result;
 9     }
10     
11     void recursiveSubsets(vector<vector<int> > &result, vector<int> &cur, const vector<int> &s, size_t idx) {
12         if(idx == s.size()) {
13             result.push_back(cur);
14         } else {
15             size_t cnt = 1;
16             size_t next = idx+1;
17             while(next < s.size() && s[next] == s[idx]) {
18                 ++cnt;
19                 ++next;
20             }
21             
22             for(size_t n = 0; n <= cnt; ++n) {
23                 for(int i = 0; i < n; ++i) 
24                     cur.push_back(s[idx]);
25                 recursiveSubsets(result, cur, s, next);
26                 for(int i = 0; i < n; ++i) 
27                     cur.pop_back();
28             }
29         }
30     }
31 };

 


联系
我们