首页 > 代码库 > Leetcode | Subsets I & II
Leetcode | Subsets I & II
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 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。