首页 > 代码库 > Leetcode | Subsets I & II

Leetcode | Subsets I & II

2024-07-03 07:23:40   223人阅读

Subsets I

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

Method I

我的做法是产生只有1个数的subset，然后产生有两个数的subset。这里有这么一层关系：

n+1个数的subset=前n个数的subset + 前n个数的subset都加上第n个数

比如 S=[1,2,3]，产生的序列如下：

[] ------------[]

[1]-----------[] [1]

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

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

为了保证所有集合是升序的，一开始需要对S进行排序。

 1 class Solution {
 2 public:
 3     vector<vector<int> > subsets(vector<int> &S) {
 4         vector<vector<int> > ret;
 5         vector<int> v;
 6         ret.push_back(v);
 7         sort(S.begin(), S.end());
 8         for(int i = 0; i < S.size(); ++i) {
 9             int n = ret.size();
10             for (int j = 0; j < n; ++j) {
11                 vector<int> nv(ret[j]);
12                 nv.push_back(S[i]);
13                 ret.push_back(nv);
14             }
15         }
16         
17         return ret;
18     }
19 };

Method II

递归。每碰到一个数，要么加进去，要么不加进去。最终产生所有集合。

 1 class Solution {
 2 public:
 3     vector<vector<int> > subsets(vector<int> &S) {
 4         sort(S.begin(), S.end());
 5         vector<int> v;
 6         recursive(S, 0, v);
 7         return ret;
 8     }
 9     
10     void recursive(vector<int> &S, int i, vector<int> &v) {
11         if (i == S.size()) {
12             ret.push_back(v);
13             return;
14         }    
15         recursive(S, i + 1, v);
16         
17         v.push_back(S[i]);
18         recursive(S, i + 1, v);
19         v.pop_back();
20     }
21     
22 private:
23     vector<vector<int> > ret;
24 };

 


联系
我们