首页 > 代码库 > 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 void quickSort(int []S,int startIndex,int endIndex){ if(startIndex>=endIndex){ return; } int middleIndex=(startIndex+endIndex)/2; int p=S[middleIndex]; S[middleIndex]=S[startIndex]; S[startIndex]=p; int i=startIndex+1; int j=endIndex; for(;i<j;){ while(i<j) { if(S[i]>=S[startIndex]) { break; } i++; } while(i<j) { if(S[j]<S[startIndex]) { break; } j--; } p=S[i]; S[i]=S[j]; S[j]=p; } if(S[i]>S[startIndex]) { i--; } p=S[i]; S[i]=S[startIndex]; S[startIndex]=p; quickSort(S,startIndex,i-1); quickSort(S,i+1,endIndex); } public List<List<Integer>> subsets(int[] S) { List<List<Integer>> result=new LinkedList<List<Integer>>(); List<List<Integer>> tmp=new LinkedList<List<Integer>>(); List<Integer> p=new LinkedList<Integer>(); result.add(p); if(S==null||S.length<=0) { return result; } int LEN=S.length; quickSort(S,0,LEN-1); for(int i=0;i<LEN;i++){ tmp.clear(); for(List<Integer>list:result){ p=new LinkedList<Integer>(); p.addAll(list); p.add(S[i]); tmp.add(p); } result.addAll(tmp); } return result; } }
Subsets
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。