首页 > 代码库 > Subsets
Subsets
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], [] ]
public class Solution { public List<List<Integer>> subsets(int[] S) { int len=S.length; ArrayList<ArrayList<Integer>> res=new ArrayList< ArrayList<Integer> >(); //if(S==null || S.length<=0) return res; int x=1<<len; for(int i=0;i<x;i++){ res.add(getSubset(S,i)); } Comparator<ArrayList<Integer>> comparator=new Comparator<ArrayList<Integer>>() { @Override public int compare(ArrayList<Integer> a1,ArrayList<Integer> a2){ if(a1.size()>a2.size()){ return 1; } else if(a1.size()==a2.size()){ int sum1=0,sum2=0; for(Integer integer :a1){ sum1+=integer; } for(Integer integer :a2){ sum2+=integer; } if(sum1>sum2) return 1; else return 0; } else return 0; } }; Collections.sort(res, comparator); ArrayList<List<Integer>> result=new ArrayList<List<Integer>>(); result.addAll(res); return result; } public ArrayList<Integer> getSubset(int []S,int x){ ArrayList<Integer> a=new ArrayList<Integer>(); for(int i=S.length-1;i>=0;i--){ if((x&1)==1){ a.add(S[i]); } x>>=1; } //Arrays.sort(a); Collections.sort(a); return a; } }
我的思路:对子集的结果要有序,只好进行排序,最后就写成这鸟样了。题目里给的解例子,好像是不合题意的。虽然AC,但是代码确实是过于冗长了。
C++版是这样的。
class Solution { public: vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(), S.end()); vector<vector<int>> res; vector<int> d; int curr_size = 0; res.push_back(vector<int>{}); for (int &e : S) { curr_size = res.size(); for(int i = 0; i < curr_size; ++i) { d = res[i]; d.push_back(e); res.push_back(d); } } return res; } };
高手是这样解的:
def subsets(self, S): res = [[]] S.sort() for e in S: res = res+[l+[e] for l in res] return res
这就是差距啊,所以还得努力学习啊。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。