BackTracking

回溯法的核心思想是当对一个数组第一个元素递归到最后一个字符的时候利用自底向上的方法，逐步删除每一个字符回到最初的状态，然后再以同样的方法应对下一个元素。主要写几道题，后面会有更多的补充：

Subsets:

以[1,2]的关于第一个元素的回溯为例，

程序运行，首先加入的是：[], 空集，然后list里面增加元素[1],这时候程序运行到26行，进行第一层递归，在递归中，将[1]list 加入到res里，然后加入下一个元素到list里,现在list里有[1,2]，然后再进行下一次递归，在这次递归中[1,2]list加入了res里，由于此时nums.length == i，所以这层递归完成，返回到上一层递归，上一层递归将[1,2]里的最后一个元素删除，list里还剩下[1]，返回到第一层递归，第一层递归里把list里的[1]删除，返回到最初的状态[]。然后循环进行到i=1的状态进入下一次循环，回溯方法一样。 

所以这种程序的写法，当你想让程序在整个递归到最后一层自底向上做什么的时候，就把那段程序写在递归语句的后面，如果你想在进行下一次递归之前做什么就把那些话写在下一次递归的前面。

Subset II：

这个问题跟上面这道题基本是一样的思路，只是因为题目里存在了重复元素，所以涉及到去重的问题，比如

[1,2(0),2(1)]和[1,2(1),2(0)]

同样的原理：

这种情况下，当在进行下一次递归的时候首先先check一下是否即将要加的元素是重复元素，如何判断呢？两个条件：

1.目前的位置不是本次循环的起始位置

2.现在这个元素和前一个加进来的元素相同

permutation：

方法基本一样， 但是需要三个不同的条件：

1.只有在数量等于当前数量的时候才会输入到res里

2.必须每次都从循环的第一个点重新递归

3.在下一次递归开始之前判断是否要结束进一步的递归，否则将陷入死循环，而跳出的条件就是不加入相同的元素。

permutation II：

与上题相同的条件，不同的是怎么判断重复元素是不同的元素呢？

需要加一个变量，每当这个变量被visit过之后把这个变量标为1，但是这样会存在一个问题，就是当一个元素的循环进行完的时候，第二个元素的循环就不会再加进新的元素了，因为所有的元素都被标为了1，所以在递归回溯的时候要把这些元素再全部标称visit点0， 这样判断是否重复元素的方法就包含三个条件：

1.这不是初始的位置

2.这个元素的值和前一个元素的值相同

3.这个元素的前一个元素还没被visit过（新的循环里这个元素不要被加进来）

题目还有latter combination of Phone number,Palindrome Partitioning,Restore IP Address,Combination Sum, Generate Parentheses, N-queen, Generalized Abbreviation, grey code之类， 之后会把更多的题补充进来。