17. Letter Combinations of a Phone Number
這道題在string分類里已經(jīng)寫過了奸攻，有遞歸和非遞歸兩種方法斤儿，思路都是先從string里只有一個(gè)數(shù)字開始筛圆，得到一個(gè)結(jié)果决摧，再不斷向結(jié)果里添加新的數(shù)字字符
39. Combination Sum
要注意backtracking有可能是遞歸和非遞歸政基，這道題就屬于遞歸地backtracking思杯。找出所有和等于target的數(shù)字組合胜蛉，同一個(gè)數(shù)字可以重復(fù)使用，這點(diǎn)就說明我們每次遞歸都要從頭進(jìn)行掃描數(shù)組色乾，屬于NP問題誊册。
- 因?yàn)樾露x的遞歸函數(shù)中要用到原函數(shù)的各個(gè)變量，所以變量應(yīng)該定義為self形式
- 要先給數(shù)組進(jìn)行排序
- 為了避免出現(xiàn)重復(fù)元素：[2,2,3], [3,2,2], [2,3,2]等暖璧，要在循環(huán)中添加一個(gè)if檢查
if path and c < path[-1]: continue, 因?yàn)槲覀円呀?jīng)對(duì)數(shù)組排序了案怯，所以path中的數(shù)字也都是有序的，如果c < path[-1]澎办，就證明我們已經(jīng)使用完了這個(gè)數(shù)字c殴泰，所以continue - 當(dāng)某一個(gè)c大于target時(shí)，要break浮驳，因?yàn)榕判蚝? c之后的數(shù)字肯定也都大于target
40. Combination Sum II
思路與上一道題相同悍汛，只是這道題要求每個(gè)數(shù)字只能使用一次。所以要向backtracking函數(shù)中多傳入一個(gè)index參數(shù)至会，并且每次迭代時(shí)進(jìn)行更新index+1
[2,5,2,1,2] 5
輸出[[1,2,2],[1,2,2],[1,2,2],[5]]
expected: [[1,2,2],[5]]
- 當(dāng)出現(xiàn)數(shù)組中有多個(gè)重復(fù)數(shù)字時(shí)离咐，為避免上述情況，一定要添加相鄰重復(fù)元素判斷：
if i > index and nums[i] == nums[i-1]: continue
在這里我們還是需要在每一次for循環(huán)前做一次判斷奉件，因?yàn)殡m然一個(gè)元素不可以重復(fù)使用宵蛀，但是如果這個(gè)元素重復(fù)出現(xiàn)是允許的，但是為了避免出現(xiàn)重復(fù)的結(jié)果集县貌，我們只對(duì)于第一次得到這個(gè)數(shù)進(jìn)行遞歸术陶，接下來(lái)就跳過這個(gè)元素了，因?yàn)榻酉聛?lái)的情況會(huì)在上一層的遞歸函數(shù)被考慮到煤痕，這樣就可以避免重復(fù)元素的出現(xiàn)梧宫。這個(gè)問題可能會(huì)覺得比較繞，大家仔細(xì)想想就明白了哈摆碉。
216. Combination Sum III
給一個(gè)k, 一個(gè)n塘匣，candidates是從1到9，要求k個(gè)數(shù)相加正好等于n巷帝。感覺比ii還稍微簡(jiǎn)單一些忌卤，不能使用重復(fù)元素，candidates里也沒有重復(fù)元素楞泼。只需要在每次backtracking時(shí)多傳入一個(gè)參數(shù)k驰徊，并且每次都對(duì)k進(jìn)行更新就可以了
self.bt(i+1, path + [self.candidates[i]], k -1, n - self.candidates[i])
將path添加到結(jié)果中的條件是：
if n == 0 and k == 0: self.res.append(path)
93. Restore IP Addresses
這道題其實(shí)屬于DFS笤闯，actually我也不知道它到底是什么分類....
思路是這樣的，先clarify一下什么是有效的ip地址棍厂，ip地址由4段組成颗味，每段的數(shù)字不能超過255，且不能以0開頭勋桶，除非數(shù)字本身就是0.
- 思路是在dfs函數(shù)中，每次for循環(huán)取一個(gè)不到4位的substring侥猬，用isvalid函數(shù)檢測(cè)它是否valid例驹，如果valid，我們就move on, 用除去這個(gè)substring之外的string作為新的參數(shù)退唠，并將temp更新鹃锈，不要忘了點(diǎn)以及將count加1（count 最初從1開始）
self.dfs(s[i:], temp + substr + '.', res, count +1) - 當(dāng)count=4時(shí)，我們就append temp到res中瞧预，但此時(shí)也不要忘了檢測(cè)isvalid(s)并且append的時(shí)候要加上s
res.append(temp + s) - 每次取不超過4位的substring屎债，所以for循環(huán)的循環(huán)范圍是
for i in range(1,5) - 在for循環(huán)里要加一個(gè)判斷，
if i < len(s):因?yàn)檩斎氲膕有可能非常短
46. Permutations
思路很清楚垢油，從只有1個(gè)數(shù)字時(shí)開始盆驹，不斷加入新的數(shù)字。新加入的數(shù)字可插入的地方是從0到n+1的滩愁，這里假設(shè)之前的組合長(zhǎng)度為n躯喇。維護(hù)一個(gè)res數(shù)組，里邊存放已經(jīng)存在的數(shù)字組合硝枉，新加入數(shù)字后廉丽，就對(duì)每個(gè)組合進(jìn)行遍歷插入，并將插入后的新組合append到new_res中妻味，new_res是中間數(shù)組正压，每一輪數(shù)字插入結(jié)束后，邊將new_res賦給res
- 每次插入后將結(jié)果append到new_res中责球，就不改變?cè)瓉?lái)組合的形式焦履，所以原來(lái)的組合可以進(jìn)行下一種插入。
- 插入的方式：
new_res.append(item[:i] + [n] + item[i:])
47. Permutations II
跟上一題的區(qū)別就在于雏逾，每插入一個(gè)數(shù)字之后裁良，先將它append給一個(gè)temp數(shù)組，判斷如果temp數(shù)組不在new_res里時(shí)校套，才new_res.append(temp)
78. Subsets
我們先來(lái)說說遞歸解法价脾，主要遞推關(guān)系就是假設(shè)函數(shù)返回遞歸集合，現(xiàn)在加入一個(gè)新的數(shù)字笛匙，我們?nèi)绾蔚玫桨聰?shù)字的所有子集侨把。其實(shí)就是在原有的集合中對(duì)每集合中的每個(gè)元素都加入新元素得到子集犀变，然后放入原有集合中（原來(lái)的集合中的元素不用刪除，因?yàn)樗麄円彩呛戏ㄗ蛹┣锉６Y(jié)束條件就是如果沒有元素就返回空集（注意空集不是null获枝，而是沒有元素的數(shù)組）就可以了。時(shí)間和空間都是取決于結(jié)果的數(shù)量骇笔，也就是O(2^n)
77. Combinations
用DFS在leetcode上總是會(huì)超時(shí)省店，但是方法應(yīng)該是沒有問題的
79. Word Search
注意字母不可以重復(fù)使用，所以在進(jìn)行搜索鄰居之前笨触，要先將
temp = board[i][j], board[i][j] = ' '
搜索完鄰居之后要再把它的值給賦回去board[i][j] = temp
DFS函數(shù)里返回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]是指單詞對(duì)應(yīng)不上時(shí)懦傍，就返回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.
在二進(jìn)制的左邊位加1芦劣，就相當(dāng)于在十進(jìn)制中加上2**i, i是二進(jìn)制中的第幾位粗俱，注意一定要是倒著數(shù)的
二進(jìn)制：01-->101 相當(dāng)于 十進(jìn)制：1-->5 ： 1+2^2=5
131. Palindrome Partitioning
還是dfs+backtracking，這道題不需要傳index進(jìn)去
357. Count Numbers with Unique Digits
n不能大于10虚吟， 因?yàn)橐还仓挥袕?到9這10個(gè)數(shù)寸认，n如果大于10了，就一定會(huì)出現(xiàn)重復(fù)位串慰。
這更像一道概率題偏塞，一位一位的看，從最左邊開始邦鲫，最左邊這位可以有9個(gè)選擇（除了0）烛愧，左邊第二位也可以有9個(gè)選擇（包含了0），左邊第三位可以有8個(gè)選擇掂碱，左邊第四位可以有7個(gè)選擇怜姿，一直到最后一位，也就是第10位疼燥，只有一個(gè)選擇沧卢。
先對(duì)n的范圍進(jìn)行判斷，如果n > 10醉者，就將n賦值為10.
然后用for循環(huán)循環(huán)n次但狭，每次計(jì)算所有可能的數(shù)字：
for i in range(n): product *= choices[i] res += choices[i] return res
60.Permutation Sequence
第一種方法是窮舉出所有permutation，然后返回第K個(gè)撬即。
第二種方法是找出其中的數(shù)學(xué)規(guī)律：
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!
