Given a set of distinct integers, return all possible subsets.
If S = [1,2,3], a solution is:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
SOLUTION:
好些天没来更新了，今天开始更新一下搜索相关的内容，这个subsets就是比较经典的几个题。
说到搜索，当然先要理解递归，递归时解决搜索问题最直接的方法，包括图上搜索用BFS，subsets，permutations相关的用DFS。
递归要注意几个问题，也就是考虑递归问题时的思维方式问题，理解递归是什么。
递归简而言之就是自己调用自己，在思维上，主要就是想清楚，在这一层时递归做了什么，完全不需要考虑上一步跟下一步递归要做什么，想清楚之后传递给下一层就行了。
下面是递归方法：
1，需要递归时，要理清递归辅助helper是用来做什么的定义：比如这个subsets，那么递归定义是helper(result, list, nums, pos)，将以list开头的subsets放入result里，int pos的目的是确保递归不选重复的。
2， 如何把大问题变到小问题。
3， 出口，极端小的情况下返回什么，或者做什么事儿。
下面就用这个题来具体说明这个过程。具体看comments
class Solution { /** * @param S: A set of numbers. * @return: A list of lists. All valid subsets. */ public ArrayList<ArrayList<Integer>> subsets(int[] nums) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if (nums == null || nums.length == 0){ return result; } ArrayList<Integer> list = new ArrayList<Integer>(); //由于题目要求升序排列，所以要排序一下，另外几本上搜索的都要排序一下，比较方便 Arrays.sort(nums); //存入null开头的list，进入递归函数 helper(result, list, nums, 0); return result; } //递归函数，定义：把list开头的subsets放进result里 private void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list, int[] nums, int pos){ //递归过程：局部操作，把list deep copy，存进result里面（程序开始先存入null，之前最开始list是null） result.add(new ArrayList<Integer>(list)); // for loop，把1开头，把2开头，把3开头的都加入list，但是上面往result里面添加时候没有限制约束，所以每加一个数字就添加进result一次，但是由于有pos指针，所以记录了从1到2的分岔点位置 for (int i = pos; i < nums.length; i++){ list.add(nums[i]); helper(result, list, nums, i + 1); list.remove(list.size() - 1); } } }
原文：http://www.cnblogs.com/tritritri/p/4918980.html
