在一亩三分地上看到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之类的。非常典型。
睡觉。
