backtracking类型题目总结

subsets 这道题属于backtracking 类的模板


subsets II 与i不同的是有重复的数字， 例如[1,2(1)] [1,2(2)]情况相同， 递归过程中每次新选取的可以是和递归数组相同的，（比如nums是[1，2，2，2］ 当前递归栈是［1，2（1）］ 新加入的［1，2(1), 2(2)]是合法的） 但是后面的元素就不能相同了（［1, 2(1), 2(3)]就不合法 因为重复了）。

if ( i != pos && num[i] == num[i - 1]) {
                continue;
            }    

用这个方法防止重复。


permutations

与subset不同的是递归传入参数每次从0开始， 为了避免重复 需要构建一个boolean[] 以记录哪个点访问过

permutations II与I 不同的是出现了重复的问题， 所以如果当前元素与之前元素相同 而之前的元素没有访问过 说明相似的情况已经出现过 要避免再出现 所以用

if(i > 0 && num[i] == num[i-1] && visit[i-1] == false ){
                continue;
            }

Combinations

combination sum 递归条件是 target = 0 加入结果 〈0就return

Combination Sum II


Generate Parentheses  返回条件是left 和right都为0
递归条件有两个： 1. left › 0时候可以选择增加left 2. left ‹ right 时 可以增加right

Letter Combinations of a Phone Number

Restore IP Addresses

Palindrome Partitioning


N-Queens I

N-Queens II

Word Search

Word Break II 

Path Sum II
先把给定数组排序 Arrays.sort()

1. 递归返回条件 
在permutation（排列）和combination时候 要当数组里面元素和所给元素数相等时候返回，
combination sum 时候则需要当target=0时候返回。

  2. 递归的时候传入什么样的参数 (0, pos or pos + 1)
2.1（对于在dfs内recursive的使用dfs时候 ） 如果每次是从i开始扫， 则得到的结果是不会重复的。（会出现[1,2]不会出现[2,1]）

2.2 但是如果[1,2] 和[2,1]两个重复情况都要的话, 则要每次从0开始扫.并且要加一个boolean[] visit 来记录某些点是否被访问过

  3. 是否重复选取
如果已选取[1,2(1)] 那么[1,2(2)]就是重复选取 为了确保这种情况不发生，
只要确定当前所选取的值num[i]和num[i-1]不重复就可以， 如果重复跳过num[i].
对于每次从i扫的情况 ：

if ( i != pos && num[i] == num[i - 1]) {
                continue;
            }    

对于每次从0开始扫的情况：

if (i > 0 && num[i] == num[i - 1] && !visit[i - 1]){
                continue;
                // important: if previous number have same value as (i)th
                // but have never been visited, then skip current number
            }

a. a4

a. 关于递归返回条件满足时， 往往要把结果存入arraylist， 这时arraylist.add(new(tem))。
当arraylist里存的是list这样可以引用的话要new 一下 存string int这样的就可以直接添加
b. 关于继续递归时候往往要把下层的结果存入中间变量 例如 tem.add() 然后递归helper(), 再tem.delete()
当中间变量是string 时候 再下层递归中可以直接把加入的东西带入string中 以免除这个步骤 例如Palindrome Partitioning中第二种解法