Leetcode--Backtracking
17. Letter Combinations of a Phone Number
这道题在string分类里已经写过了，有递归和非递归两种方法，思路都是先从string里只有一个数字开始，得到一个结果，再不断向结果里添加新的数字字符
39. Combination Sum
要注意backtracking有可能是递归和非递归，这道题就属于递归地backtracking。找出所有和等于target的数字组合，同一个数字可以重复使用，这点就说明我们每次递归都要从头进行扫描数组，属于NP问题。
- 因为新定义的递归函数中要用到原函数的各个变量，所以变量应该定义为self形式
- 要先给数组进行排序
- 为了避免出现重复元素：[2,2,3], [3,2,2], [2,3,2]等，要在循环中添加一个if检查
if path and c < path[-1]: continue, 因为我们已经对数组排序了，所以path中的数字也都是有序的，如果c < path[-1]，就证明我们已经使用完了这个数字c，所以continue - 当某一个c大于target时，要break，因为排序后, c之后的数字肯定也都大于target
40. Combination Sum II
思路与上一道题相同，只是这道题要求每个数字只能使用一次。所以要向backtracking函数中多传入一个index参数，并且每次迭代时进行更新index+1
[2,5,2,1,2] 5
输出[[1,2,2],[1,2,2],[1,2,2],[5]]
expected: [[1,2,2],[5]]
- 当出现数组中有多个重复数字时，为避免上述情况，一定要添加相邻重复元素判断：
if i > index and nums[i] == nums[i-1]: continue
在这里我们还是需要在每一次for循环前做一次判断，因为虽然一个元素不可以重复使用，但是如果这个元素重复出现是允许的，但是为了避免出现重复的结果集，我们只对于第一次得到这个数进行递归，接下来就跳过这个元素了，因为接下来的情况会在上一层的递归函数被考虑到，这样就可以避免重复元素的出现。这个问题可能会觉得比较绕，大家仔细想想就明白了哈。
216. Combination Sum III
给一个k, 一个n，candidates是从1到9，要求k个数相加正好等于n。感觉比ii还稍微简单一些，不能使用重复元素，candidates里也没有重复元素。只需要在每次backtracking时多传入一个参数k，并且每次都对k进行更新就可以了
self.bt(i+1, path + [self.candidates[i]], k -1, n - self.candidates[i])
将path添加到结果中的条件是：
if n == 0 and k == 0: self.res.append(path)
93. Restore IP Addresses
这道题其实属于DFS，actually我也不知道它到底是什么分类....
思路是这样的，先clarify一下什么是有效的ip地址，ip地址由4段组成，每段的数字不能超过255，且不能以0开头，除非数字本身就是0.
- 思路是在dfs函数中，每次for循环取一个不到4位的substring，用isvalid函数检测它是否valid，如果valid，我们就move on, 用除去这个substring之外的string作为新的参数，并将temp更新，不要忘了点以及将count加1（count 最初从1开始）
self.dfs(s[i:], temp + substr + '.', res, count +1) - 当count=4时，我们就append temp到res中，但此时也不要忘了检测isvalid(s)并且append的时候要加上s
res.append(temp + s) - 每次取不超过4位的substring，所以for循环的循环范围是
for i in range(1,5) - 在for循环里要加一个判断，
if i < len(s):因为输入的s有可能非常短
46. Permutations
思路很清楚，从只有1个数字时开始，不断加入新的数字。新加入的数字可插入的地方是从0到n+1的，这里假设之前的组合长度为n。维护一个res数组，里边存放已经存在的数字组合，新加入数字后，就对每个组合进行遍历插入，并将插入后的新组合append到new_res中，new_res是中间数组，每一轮数字插入结束后，边将new_res赋给res
- 每次插入后将结果append到new_res中，就不改变原来组合的形式，所以原来的组合可以进行下一种插入。
- 插入的方式：
new_res.append(item[:i] + [n] + item[i:])
47. Permutations II
跟上一题的区别就在于，每插入一个数字之后，先将它append给一个temp数组，判断如果temp数组不在new_res里时，才new_res.append(temp)
78. Subsets
我们先来说说递归解法，主要递推关系就是假设函数返回递归集合，现在加入一个新的数字，我们如何得到包含新数字的所有子集。其实就是在原有的集合中对每集合中的每个元素都加入新元素得到子集，然后放入原有集合中（原来的集合中的元素不用删除，因为他们也是合法子集）。而结束条件就是如果没有元素就返回空集（注意空集不是null，而是没有元素的数组）就可以了。时间和空间都是取决于结果的数量，也就是O(2^n)
77. Combinations
用DFS在leetcode上总是会超时，但是方法应该是没有问题的
79. Word Search
注意字母不可以重复使用，所以在进行搜索邻居之前，要先将
temp = board[i][j], board[i][j] = ' '
搜索完邻居之后要再把它的值给赋回去board[i][j] = temp
DFS函数里返回False的条件包括:
if i <0 or i >= len(board) or j<0 or j>=len(board[0]) or board[i][j] != word[0]: return False
最后的board[i][j]!=word[0]是指单词对应不上时，就返回False
89. Gray Code
感觉这道题比较讨巧，解题思路是：
https://discuss.leetcode.com/topic/17275/python-5-lines-no-recursive-just-generate-the-result 直接放别人的连接好了
We add 2^i to the corresponding number in the reversed copy of the previous array, then append it to the array each time.
在二进制的左边位加1，就相当于在十进制中加上2**i, i是二进制中的第几位，注意一定要是倒着数的
二进制：01-->101 相当于 十进制：1-->5 ： 1+2^2=5
131. Palindrome Partitioning
还是dfs+backtracking，这道题不需要传index进去
357. Count Numbers with Unique Digits
n不能大于10， 因为一共只有从0到9这10个数，n如果大于10了，就一定会出现重复位。
这更像一道概率题，一位一位的看，从最左边开始，最左边这位可以有9个选择（除了0），左边第二位也可以有9个选择（包含了0），左边第三位可以有8个选择，左边第四位可以有7个选择，一直到最后一位，也就是第10位，只有一个选择。
先对n的范围进行判断，如果n > 10，就将n赋值为10.
然后用for循环循环n次，每次计算所有可能的数字：
for i in range(n): product *= choices[i] res += choices[i] return res
60.Permutation Sequence
第一种方法是穷举出所有permutation，然后返回第K个。
第二种方法是找出其中的数学规律：
a1 = k/(n-1)!
k1 = k
a2 = k1/(n-2)!
k2 = k1 % (n - 2)!
an-1 = kn-2 / 1!
kn-1 = kn-2 / 1!
an = kn-1 / 0!
kn = kn-1 % 0!
