写这个系列是因为纪念一下去年的今天，就是2015年的9月14号，刷题第一天，今天是一周年纪念日。当时只敢做easy还得抄答案的我想啥时候能做上medium啊，事到如今，感觉都不是啥障碍了，这道题也已经做了第四遍了，抽出来的DFS递归模板放在这里总结一下。
这题内容就是就是给个数组，里面的数字都是独一无二的，把它所有的子集都输出出来。解决思路
题目中给了个例子，比如[1,2,3]，第一次抽出1，然后在1的基础上加2，再加3。加完之后再往回返，去掉3，再去掉2，发现可以加3，形成[1,3]，再到2，以此类推。
code
public class Subsets { public List > subsets(int[] nums) { //先把输出的东西摆上去。 List > result = new ArrayList<>(); //排除corner case，就是返回一空的。 if(nums == null || nums.length == 0) return result; //这个就是用来搜集每个子集的。 List list = new ArrayList<>(); dfs(result, list, 0, nums); return result; } public void dfs(List > result, List list, int start, int[] nums){ //先把当前的子集加上，这里添加的语法我命名为『照相法』 result.add(new ArrayList<>(list)); //注意这里要从start位置开始循环，否则就是stackoverflow for(int i = start; i < nums.length; i++){ //添加start位置的数字 list.add(nums[i]); //开始递归，比如把1加上去之后，就稳住1，找后面比如2. dfs(result, list, i+1, nums); //backtrack，就是把之前加上的去掉，相当于往回走，比如之前加到1，2，3 //就把3去掉，然后再找。 list.remove(list.size()-1); } }}
复杂度分析
算法课讲过，这个复杂度是指数次，能实现出来就行了，没法优化。
最后再说两句
这题就是模板，DFS的模板，就是一个容器来回抓，容器的容器每次把这个容器记录下来。还有递归的debug就是人工模仿IDE，一步一步走。
稍有不同，就是数组里面的数字可能有重复，同时要求子集输出不能用重复的元素，一个非常典型的follow up。
解决思路
重点在于判断重复数字，把重复的情况跳过去。模板还是一样的。
code
public class SubsetsII { public List > subsetsWithDup(int[] nums) { List > result = new ArrayList<>(); if(nums == null || nums.length == 0) return result; //这里就需要排序了，给以后跳过重复数字埋下伏笔 Arrays.sort(nums); //剩下都是一样的 List list = new ArrayList<>(); dfs(result, list, 0, nums); return result; } public void dfs(List > result, List list, int start, int[] nums){ result.add(new ArrayList<>(list)); for(int i = start; i < nums.length; i++){ //关键就在这一句，每次循环起始的数字不能和之前重复。 if(i > start && nums[i] == nums[i-1]) continue; list.add(nums[i]); dfs(result, list, i+1, nums); list.remove(list.size()-1); } }}
复杂度分析
不分析了，反正指数次。
最后再说两句
这里注意用好模板，循环的时候把起始的start写成了0，直接就爆了。