首页 > 代码库 > leetcode: Subsets & Subsets II
leetcode: Subsets & Subsets II
Subsets
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], [] ]
class Solution { public: vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(),S.end()); vector<int> buf; vector<vector<int> > res; subset(S,0,buf,res); return res; } private: void subset(vector<int> &S, int start, vector<int> &buf, vector<vector<int> > &res) { if(start == S.size()) { res.push_back(buf); return; } subset(S,start+1,buf,res); buf.push_back(S[start]); subset(S,start+1,buf,res); buf.pop_back(); } };
Subsets II
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], [] ]
class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> &S) { sort(S.begin(),S.end()); vector<int> buf; vector<vector<int> > res; subset(S,0,buf,res); //res.push_back(vector<int> {}); return res; } private: void subset(vector<int> &S, int start, vector<int> &buf, vector<vector<int> > &res) { if(start == S.size()) { res.push_back(buf); return; } int nextStart = distance(S.begin(),upper_bound (S.begin()+start, S.end(), S[start])); for(int i=0;i<(nextStart-start);i++) { buf.push_back(S[start]); } for(int i=(nextStart-start);i>0;i--) { subset(S,nextStart,buf,res); buf.pop_back(); } subset(S,nextStart,buf,res); } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。