首页 > 代码库 > [LeetCode系列]子集枚举问题[无重复元素]
[LeetCode系列]子集枚举问题[无重复元素]
给定一组数(未排序), 求它们的所有组合可能.
如给定{1 2 3}, 返回:
[ [] [1] [2] [3] [1 2] [1 3] [2 3] [1 2 3] ]
算法思路:
- 对数组排序, 从小到大;
- 令 i = 0, 对已有组合v从后往前进行如下操作
- v的最后1个组合内加入第i个元素;
- 将新组合加入到v中
算法的理解可以通过一个例子来看:
给定S = {1 2 3},
v = [[]]
i = 0, j = 1, v = [[] [1]] // back().push_back(S[0])
i = 1, j = 2, v = [[] [1] | [1 2] [2]] // j = 2, add 2 new elems
i = 2, j = 4, v = [[] [1] [1 2] [2] | [2 3] [1 2 3] [1 3] [3]]
相同颜色前者为原有元素, 后者为增加后的元素.
代码:
1 class Solution { 2 public: 3 vector<vector<int> > subsets(vector<int> &S) { 4 sort(S.begin(), S.end()); 5 vector<vector<int> > v(1); 6 for(int i = 0; i < S.size(); ++i) { 7 int j = v.size(); 8 while(j-- > 0) { 9 v.push_back(v[j]);10 v.back().push_back(S[i]);11 }12 }13 return v;14 }15 };
[LeetCode系列]子集枚举问题[无重复元素]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。