题目：
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], [] ] 题解：一个思路就是套用combination的方法，其实combination那道题就是在求不同n下的subset，这里其实是要求一个集合罢了。例如k=3，n=1，用combination那道题的方法求得集合是[[1], [2], [3]]； k=3, n=2, 用combination那道题的方法求得集合是[[1, 2], [1, 3], [2, 3]] k=3, n=3, 用combination那道题的方法求得集合是[[1,2,3]]所以上述3个集合外加一个空集不就是[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]么？只需要在combination的外面加个循环即可。代码如下： 1 public static void dfs(int[] S, int start, int len, ArrayList<Integer> item,ArrayList<ArrayList<Integer>> res){ 2 if(item.size()==len){ 3 res.add(new ArrayList<Integer>(item)); 4 return; 5 } 6 for(int i=start; i<S.length;i++){ 7 item.add(S[i]); 8 dfs(S, i+1, len, item, res); 9 item.remove(item.size()-1); 10 } 11 12 } 13 14 public static ArrayList<ArrayList<Integer>> subsets(int[] S) { 15 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>> (); 16 ArrayList<Integer> item = new ArrayList<Integer>(); 17 if(S.length==0||S==null) 18 return res; 19 20 Arrays.sort(S); 21 for(int len = 1; len<= S.length; len++) 22 dfs(S,0,len,item,res); 23 24 res.add(new ArrayList<Integer>()); 25 26 return res; 27 } Reference：http://blog.csdn.net/worldwindjp/article/details/23300545 底下是另外一个很精炼的算法。 1 public static void dfs(int[] S, int start, ArrayList<Integer> item,ArrayList<ArrayList<Integer>> res){ 2 for(int i=start; i<S.length;i++){ 3 item.add(S[i]); 4 res.add(new ArrayList<Integer>(item)); 5 dfs(S,i+1, item,res); 6 item.remove(item.size()-1); 7 } 8 9 } 10 11 public static ArrayList<ArrayList<Integer>> subsets(int[] S) { 12 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>> (); 13 ArrayList<Integer> item = new ArrayList<Integer>(); 14 if(S.length==0||S==null) 15 return res; 16 17 Arrays.sort(S); 18 dfs(S,0,item,res); 19 res.add(new ArrayList<Integer>()); 20 21 return res; 22 } Reference：http://blog.csdn.net/u011095253/article/details/9158397http://www.cnblogs.com/springfor/p/3879830.html转载于:https://www.cnblogs.com/hygeia/p/4627752.html
