首页 > 代码库 > 42. Subsets && Subsets II
42. 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<vector<int> > vec(1); for(size_t id = 0; id < S.size(); ++id) { int n = vec.size(); while(n-- > 0) { vec.push_back(vec[n]); vec.back().push_back(S[id]); } } return vec; }};
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], []]
思想： 排序后，按照 1 的方法。但是若前面的数字与本数字相同，则只读取含有前面数字的每个子集，把自身放在后面作为一个新的子集。
class Solution {public: vector<vector<int> > subsetsWithDup(vector<int> &S) { sort(S.begin(), S.end()); vector<vector<int> > vec(1); size_t prePos, endTag; prePos = endTag = 0; for(size_t id = 0; id < S.size(); ++id) { if(id > 0 && S[id] != S[id-1]) endTag = 0; else endTag = prePos; size_t n = vec.size(); prePos = n; while(n > endTag) { --n; vec.push_back(vec[n]); vec.back().push_back(S[id]); } } return vec; }};
42. Subsets && Subsets II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。