好贷网好贷款

生成一个集合的所有子集 Subset

发布时间:2016-12-3 12:43:02 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"生成一个集合的所有子集 Subset",主要涉及到生成一个集合的所有子集 Subset方面的内容,对于生成一个集合的所有子集 Subset感兴趣的同学可以参考一下。

典型的递归状态生成问题。类似于全排列的生成问题。 问题一:无重复元素集合的子集。Given a set of distinct integers, S, return all possible subsets. 思路:借助一个只含0和1的数组来表示存在状态。不断切换状态进行深层递归,在递归最深处生成子集。 class Solution { public: vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(), S.end()); vector<vector<int> > v; vector<int> t; for(int i=0;i< S.size();i++) t.push_back(0); fun(S, t, 0, v); return v; } void fun(vector<int> &s, vector<int> &t, int k, vector<vector<int> > &v) { if(k == s.size()) { vector<int> tmp; for(int i=0; i<k; i++) if(t[i] != 0) tmp.push_back(s[i]); v.push_back(tmp); } else { t[k] = 0;//注意更改当前层次的状态 fun(s, t, k+1, v); t[k] = 1;//注意更改当前层次的状态 fun(s, t, k+1, v); } } }; 问题二:有重复元素集合的子集。Given a collection of integers that might contain duplicates, S, return all possible subsets. class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> &S) { vector<vector<int> > result; vector<int> now; sort(S.begin(), S.end());//排序 set<vector<int> > s; backtrack(s, now, S, 0); set<vector<int> >::iterator it = s.begin(); for(;it != s.end();it++) result.push_back(*it); return result; } void backtrack(set<vector<int> > &result, vector<int> &now, vector<int> &S, int idx) { if(idx == S.size()) { result.insert(now);//set去重复 return; } backtrack(result, now, S, idx+1); now.push_back(S[idx]); backtrack(result, now, S, idx+1); now.pop_back(); } };

上一篇:一个strcpy 的溢出例子
下一篇:ava.util.Date和java.sql.Date 一点区别

相关文章

相关评论