首页 > 代码库 > [LeetCode系列]子集枚举问题[有重复元素]
[LeetCode系列]子集枚举问题[有重复元素]
给定一组数(未排序, 可能有重复元素), 求出所有可能的组合.
算法和无重复元素的相似.
唯一需要注意的是, 如果当前的数字和之前的相同, 算法就只会在结尾数字是此数字的组合后加上此数字.
比如现在是[[] [1] [1 2] [2]], 当前数字是2, 就只会增加[1 2 2] [2 2]
代码:
1 class Solution { 2 public: 3 vector<vector<int> > subsetsWithDup(vector<int> &S) { 4 sort(S.begin(), S.end()); 5 vector<vector<int>> result(1); 6 int oldval=S[0]; 7 int oldj=0; 8 for(int i=0; i<S.size(); i++){ 9 int temp=oldj;10 if(S[i]!=oldval){11 oldval=S[i]; temp=0;12 }13 int j=result.size();14 oldj=j;15 while(j-->temp){16 //note temp here help avoid creating duplicate subsets17 result.push_back(result[j]);18 result.back().push_back(S[i]);19 }20 }21 return result;22 }23 };
[LeetCode系列]子集枚举问题[有重复元素]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。