首页 > 代码库 > Leetcode: Subsets & SubsetsII
Leetcode: Subsets & SubsetsII
Subsets Description:
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], []]
分析: 首先注意集合内的元素都是不同的整数,所以尽情产生就好了。产生subsets时,基本思想是由小到大,先产生小的,再
利用小的产生大集合。具体来说,就是先用0个,1个,...来生成子集然后对新的元素,只要把前面的所有子集中加上个新元素,然后和之前
的子集和在一起,就是所有子集了。这里能直接加元素,就是因为没有重复的整数
1 class Solution { 2 public: 3 vector<vector<int> > subsets(vector<int> &S) { 4 sort(S.begin(),S.end()); 5 vector<vector<int> > result; 6 7 vector<int> comb; 8 result.push_back(comb); 9 10 for(int i=0;i<S.size();i++)11 {12 int nows = result.size();13 for(int j=0;j<nows;++j)14 {15 comb = result[j];16 comb.push_back(S[i]);17 result.push_back(comb);18 }19 }20 21 return result;22 }23 };
SubsetsII Description:
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], []]
分析:这个题目和上面的唯一区别就在于集合中有相同的元素, 然后再遇到后面是相同元素的时候,添加到子集中产生新子集时,相当于要选择往里面添加几个这个元素。
这里直接用跟上面一样的方法,只是再最后把它们放到set中,去除重复元素,然后再放回vector中返回。这种方法好像有点萌蠢。。 但是呢,根据上面的分析,还有一种
做法,就是将vector中所有元素遍历一遍,放到map中,map中key就是元素值,value是重复的个数,然后就用这个map开始同样的过程,只是产生新的子集的时候
,根据value值,分别产生加不同数量的该元素。
class Solution {public: vector<vector<int> > subsetsWithDup(vector<int> &S) { sort(S.begin(),S.end()); set<vector<int> > setres; vector<vector<int> > results; vector<int> comb; results.push_back(comb); for(int i=0;i<S.size();i++) { int nows = results.size(); for(int j=0;j<nows;++j) { comb = results[j]; comb.push_back(S[i]); results.push_back(comb); } } setres.insert(results.begin(),results.end()); results.assign(setres.begin(),setres.end()); return results; }};
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。