在一亩三分地上看到leetcode里有样的summary，今天早上看了一下，下面是我的总结。

Subsets

下面的代码是很久前写的了，当时是什么都不懂。。

再看这个代码，发现有个奇怪的地方就是它的递归没有显式的Terminator（终止条件），这里的for循环就相当于terminator，因为start每次都会+1。所以for循环不满足之后，dfs函数执行完了就会自动return，所有的return都可以看成终止条件，就算是函数执行完了之后的return(void的话就是隐式return)也一样。那么如果i不+1进入下一次dfs，就会栈溢出。

另外，我以为解集会是[],[1],[2],[3]...这样，其实是：

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]。

还是跟N queens那种一样，画个N * N的matrix来理解。
注意这里是有「归去来兮」的，因为cell进入下一次递归时是同一个引用。

另外，这题跟普通dfs不同的是，普通dfs一般是走到max depth才backtracking，这题是没有判断，直接把遇到的解加到res里。那为什么不会出现重复解？因为i每次都+1，不会走回头路。类似右上三角（这么描述可能只有我自己能听懂。。。）

--
Jun 16 review : 有点像二叉树层序遍历的递归，每次来到新的一层就新建list，但是这题没有tree的level那么好区分，而是直接利用递归的栈来在以前的基础上用for循环移动数据并添加。这就是为什么结果是[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]] 这种，而且需要手动恢复现场。

为什么1，2，3之后会连续remove两次，然后add 3呢？因为第一，走到第三层之后进入第四层递归发现for循环不满足了，于是回到第三层，执行dfs后面的代码，remove掉末尾元素；第二，remove这句话完成之后，第三层的任务结束了，return void，回到第二层继续执行dfs后面的代码，自然就又remove掉2了。然后第二层的指针指向3，继续dfs。

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> cell = new ArrayList<>();
        dfs(nums, result , cell , 0);
        return result;
    }

    public void dfs(int [] nums , List<List<Integer>> result , List<Integer> cell , int start){
        //add 放在for的外面,new一个
        result.add(new ArrayList<>(cell));
        //start指针的作用，是在dfs的时候向着深处走
        for(int i = start ; i < nums.length ; i ++){
            cell.add(nums[i]);
            //for中进行的dfs
            dfs(nums , result , cell , i+1);
            //backtracking
            cell.remove(cell.size()-1);
        }
    }

另，这题leetcode高票答案里还有用位运算来做的。

Subsets II

这题跟Subsets I不同的地方是，它给的nums可以有重复元素了，比如[1,2,2]。按照上一题的解法，会出现这样的解集：

[[], [1], [1, 2], [1, 2, 2], [1, 2], [2], [2, 2], [2]]

怎么避免有duplicated的解呢。其实跟Combination SumII很像，follow up也是不允许有重复解，当时是先排序，然后判重如果有重复就调过。
玛德 这题也是一个同一个套路：

public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
} 

Permutations

Subsets是「组合」，Permutations是排列。
那么这题也容易想到，跟subsets相比，把进入下一层dfs的i+1去掉就好了(同时要加上terminator哦)。但是这样一来对于[1,2,3]这样的nums，第一个解会变成[1,1,1]呀。怎么办，增加一个数组来保存是否使用过(模拟HashMap)，有点像图的遍历了。或者直接利用ArrayList的contains函数判重，如果有了就continue。但是我们知道链表的查找操作复杂度是O(n)，HashMap是O(1)，所以更推荐用前一种方法呀，虽然要进行两次恢复现场。

public List<List<Integer>> permute(int[] num) {
    if (num.length == 0) return null;
    List<Integer> cell = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    return backtracking(num, cell, result, new boolean[num.length]);

}
public List<List<Integer>> backtracking(int[] nums, List<Integer> cell, List<List<Integer>> result, boolean[] used) {
    if (cell.size() == nums.length) {
        result.add(new ArrayList<>(cell));
        return null;
    }
    for (int i = 0; i < nums.length; i++) {
        if (!used[i]) {
            cell.add(nums[i]);
            used[i] = true;
            backtracking(nums, cell, result, used);
            cell.remove(cell.size()-1);
            used[i] = false;
        }
    }
    return result;
}

九点了。。先去上班了。。以后可能得早点。

---

Permutations II

我以为这题用I 里的contains的那种方法可以AC，结果发现用它的方法打印出来的是空集。。然后看了下，原来它是在templist里(而不是result里)判断有没有用过一个数字，那对于1,1,2这样的nums，就永远找不到一个length==3的解了，所以res是空集。那可不可以直接在加入到res的时候判断是否contains呢？当然也是不行的了，因为你都找不到一个合法的解可以加入result。

那么我又想到，如果可以的话，我可以用 permutations I的那种used标记的代码，然后在res add的地方判断res解集里有没有重复的解，没有才添加。

//这说明result.contains判断的不是cell的内存地址啊，而是里面的元素
            if (!result.contains(cell))
                result.add(new ArrayList<>(cell));

我自己用[1,1,2]这样的test case测试是没问题的，但是当解集是[1,1,0,0,1,-1,-1,1]，leetcode就TLE了，我在IDE中跑发现这个解集已经非常长， 目测有几百个，那么用O(n)来查找的话肯定很耗时。

应该这样：

if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;

两种情形，
1是如果进入下一层发现这个slot的数字在前面已经用过了，就continue；
2是发现这个slot没用过，但是这个slot和前一个slot的数字相等，而且前一个slot没用过，continue（因为这样的话 cell.add(nums[i])一定会把前一个slot的数字加进去，这样就重复了。例如[1,1,2]的test case。）

还有，不要忘了先排序!!
玛德，允许重复的follow up一般都还有点思维难度的。

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
    if(tempList.size() == nums.length){
        list.add(new ArrayList<>(tempList));
    } else{
        for(int i = 0; i < nums.length; i++){
            if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
            used[i] = true; 
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, used);
            used[i] = false; 
            tempList.remove(tempList.size() - 1);
        }
    }
}

剩下的Combination Sum，Palindrome Partitioning单独开文章写了。

总结一下，这种for循环里的dfs一般就是用来列举解集的（一串string，数组之类的可以用for遍历的），同样的题目还有n queens，word search之类的。非常典型。

睡觉。

---