首页 > 代码库 > LeetCode--Subsets II
LeetCode--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], [] ]
class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> &S) { int n = S.size(); heap_sort(S); vector<vector<int>> res; for(int k=0; k<=n; k++) { vector<int> temp(k,-1); get_res(-1,0,k,S,res,temp); } return res; } void get_res(int loc, int now, int k, vector<int>& s, vector<vector<int>>& res, vector<int>& temp) { if(k == now) { res.push_back(temp); return; } int n = s.size(); temp[now] = s[loc+1]; get_res(loc+1,now+1,k,s,res,temp); for(int i=loc+2; i<=n-k+now; i++) { if(s[i] == s[i-1]) continue; temp[now] = s[i]; get_res(i,now+1,k,s,res,temp); } return; } void swap(vector<int>& s, int i, int j) { int t = s[i]; s[i] = s[j]; s[j] = t; } void sink(vector<int>& s, int loc, int end) { while(loc<end) { int k=2*loc+1; if(k>end) return ; if(k<end && s[k+1]>s[k]) k++; if(s[loc] > s[k]) return ; swap(s,k,loc); loc = k; } } void heap_sort(vector<int>& s) { int n = s.size()-1; for(int i=(n-1)/2; i>=0; i--) sink(s,i,n); while(n>0) { swap(s,0,n); n--; sink(s,0,n); } } };
LeetCode--Subsets II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。