本文是對leetcode回溯題的一些模板進行整理總結，很多關于回溯的blog都會參考對回溯演算法的official definition和通用的解題步驟，如果是真的想研究這一演算法思想，按照這樣的方式來完全沒有問題，不過個人覺得如果僅僅只是為了應試，那么掌握一些解題的模板會更直接的幫助理解回溯的演算法思想，本文將舉一些簡單的例子來說明這些模板，不采用樹來描述，使得對于資料結構不太了解的讀者也相對友好，
基本思想：
回溯問題是對多叉樹的深度搜索，遇到不滿足條件的節點則回退，遞回的搜索答案，在遞回呼叫前，嘗試一種可能的方案，那么在遞回呼叫的時候，函式的開始，有判斷陳述句，如果這種方案可行，記錄下這種方案，并且return，否則，繼續進行嘗試，找到滿足條件的解以后，回退到之前的選擇，
常見模板：
1、全排列問題
一般在回溯的程序中，不斷縮小原來陣列的范圍并添加至track中，直至列舉完所有的元素，滿足條件的添加到result陣列中, 模板如下
1 def problem(nums): 2 res = [] 3 def backtrack(nums, track): 4 if (判斷滿足題目所給的條件): 5 res.append(track[:]) #這里必須傳入track的拷貝，track[:], 否則答案全是空 6 return 7 for i in range(len(nums)): 8 backtrack(nums[:i] + nums[i+1:], track + nums[i]) 9 backtrack(nums, []) 10 return 題目需要的res相關的引數，輸出本身，長度，或者其他的
####https://www.cnblogs.com/HMJIang/####
以下兩題為實戰中套用框架解題
Leetcode 46 全排列
由于是全排列，只要沒得選了，那就是我們所需的答案，加入result并且return
1 class Solution: 2 def permute(self, nums: List[int]) -> List[List[int]]: 3 res = [] 4 def backtrack(nums, track): 5 if not nums: 6 res.append(track[:]) 7 return 8 for i in range(len(nums)): 9 backtrack(nums[:i] + nums[i+1:], track+[nums[i]]) 10 backtrack(nums, []) 11 return res
####https://www.cnblogs.com/HMJIang/####
Leetcode 1079 活字印刷
依舊是一個全排列的問題，差別僅僅在于，這次沒有限制需要所有的字符都要用到，而是任意長度符合條件均可，唯一的問題在于需要去掉重復的排列，直接使用集合判斷是否有重復會很方便，相比于在res陣列中用if xxx not in 要有顯著的效率的提高，
最終結果需要去掉一個空的排列，因為題目要求最后的結果非空，
1 class Solution: 2 def numTilePossibilities(self, tiles: str) -> int: 3 res = set() #使用集合去重 4 def backtrack(tiles, track): 5 res.add(track) 6 for i in range(len(tiles)): 7 backtrack(tiles[:i] + tiles[i+1:], track + tiles[i]) 8 backtrack(tiles, "") 9 return len(res) - 1
####https://www.cnblogs.com/HMJIang/####
2、陣列元素不重復且陣列元素不可以重復使用的組合問題
這種問題在高中找多少種不同的組合比較常見，比如找 [1,2,3] 這樣的陣列有多少種非空的子集，那么我們按照高中的不重復不遺漏的找法，一般是先確定1，然后找2,3里面的，第一輪找出來是 [1], [1,2], [1,3], [1,2,3]，這時候對于1來說，沒有更多的元素可以和它組成子集了，那么現在去掉1，再從 [2,3]里面找剩余的，第二輪出來的是 [2], [2,3]，最后一輪從 [3] 中找，也就是 [3]，這樣我們就得到了不重復不遺漏的所有非空子集，
可以看到，這種問題，越搜索，資料范圍越小，比上一輪起始資料向后移動了一位，那么在遞回呼叫中就可以用一個index標志+1來表示現在的起始位置從上一輪+1的位置開始，框架如下
1 def problem(nums): 2 res = [] 3 def backtrack(index, track): 4 if (滿足題目中的條件): 5 res.append(track[:]) 6 return 7 for i in range(index, len(nums)): 8 backtrack(i + 1, track + [nums[i]]) 9 backtrack(0, []) #這里不一定是0，根據實際的起始條件來給 10 return res
####https://www.cnblogs.com/HMJIang/####
以下三題為實戰中用框架解題
Leetcode 77 組合
實際問題的回傳條件是每個組合內有k個數，那么就是track長度需要是k的時候回傳，由于這里題目并沒有直接給出陣列，是用1-n來代替，那么起始條件就是1，陣列用1-n的范圍來代替就好，
1 class Solution: 2 def combine(self, n: int, k: int) -> List[List[int]]: 3 res = [] 4 def backtrack(index, track): 5 if len(track) == k: 6 res.append(track[:]) 7 return 8 for i in range(index, n+1): 9 backtrack(i + 1, track + [i]) 10 backtrack(1, []) 11 return res
####https://www.cnblogs.com/HMJIang/####
Leetcode 78 子集
直接套入框架，這里每一次搜索的路徑都要記錄下來，那就記錄一下每次的路徑就行了，不需要再判斷什么時候的結果才保存
1 class Solution: 2 def subsets(self, nums: List[int]) -> List[List[int]]: 3 res = [] 4 def backtrack(index, track): 5 res.append(track[:]) 6 for i in range(index, len(nums)): 7 backtrack(i+1, track + [nums[i]]) 8 backtrack(0, []) 9 return res
####https://www.cnblogs.com/HMJIang/####
Leetcode 17 電話號碼中的字母組合
此題看上去陣列中的數可以重復，比如可以撥打“232”，但是由于是字串，順序是一定的，而且撥打第一個2和第二個2，對應的字母也可能不同，所以仍然可以看做是陣列中元素不重復且不能重復使用的問題，
用字典記錄下對應關系，之后代入框架即可，注意讀取字典鍵和值的各種括號就行，最終結果是字串的時候，track初始設為“”替代[]
1 class Solution: 2 def letterCombinations(self, digits: str) -> List[str]: 3 if not digits: 4 return [] 5 res = [] 6 dic = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'} 7 def backtrack(index, track): 8 if len(track) == len(digits): 9 res.append(track) 10 return 11 for i in range(len(dic[digits[index]])): 12 backtrack(index + 1, track + dic[digits[index]][i]) 13 backtrack(0, "") 14 return res
####https://www.cnblogs.com/HMJIang/####
3、陣列元素有重復但不可以重復使用的組合問題
這一類問題和第二種型別的問題相似，最主要的是要對結果進行去重，也就是對深搜的N叉樹進行剪枝，比如我們要找 [2,1,2,4] 有多少種不重復的子集組合，按照我們的高中知識，為了不重復不遺漏，我們應該先排序這個陣列，得到[1,2,2,4]，這時候從1開始找，第一輪是 [1], [1,2]，接下來遇到一個相同的2，我們為了不重復，會跳過它，不看，因為 len = 2 的時候，如果再選2，就會得到重復的結果，然后是 [1,4], [1, 2, 2], [1, 2, 4], [1,2,2,4]，我們在找 len=3的時候，同樣，當第二位選了第一個2以后，第二位就不再考慮選第二個2的情況，因為它們的結果相同，至此，第一輪結束，
第二輪去掉1,在[2,2,4]里面找，[2], [2,2], [2,4], [2,2,4], 第三輪去掉一個2，本來應該在[2,4]里面找，假如我們這樣找結果，會得到 [2], [2,4]，產生重復，因為 [2,4] 的情況已經包含在 [2,2,4] 中了，這就是有重復元素的情況下，我們在同一個位置進行選擇的時候，應該跳過相同的元素，否則會產生重復，第三輪實際在 [4] 里面找，得到 [4]，
框架如下
1 def problem(nums): 2 res = [] 3 nums.sort() #排序，為了后面去重做準備 4 def backtrack(index, track): 5 if (滿足題目條件): 6 res.append(track[:]) 7 for i in range(index, len(nums)): 8 ###進行剪枝，跳過相同位置重復的數字選擇 9 if i > index and nums[i] == nums[i-1]: 10 continue 11 backtrack(i + 1, track + [nums[i]]) 12 backtrack(0, []) 13 return res
####https://www.cnblogs.com/HMJIang/####
以下兩題為實戰中用框架解題
Leetcode 90 子集2
搜索路徑上所有結果全部保留，直接套入上述框架即可
1 class Solution: 2 def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: 3 res = [] 4 nums.sort() 5 def backtrack(index, track): 6 res.append(track[:]) 7 for i in range(index, len(nums)): 8 if i > index and nums[i] == nums[i-1]: 9 continue 10 backtrack(i + 1, track + [nums[i]]) 11 backtrack(0, []) 12 return res
####https://www.cnblogs.com/HMJIang/####
Leetcode 40 組合總和2
這里唯一的差別是在于需要把目標和也一起代入進遞回呼叫中，每次判斷如果是目標和就加入最終結果，加超過了目標和那就不符合，直接跳出
1 class Solution: 2 def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: 3 candidates.sort() 4 res = [] 5 def backtrack(index, track, target): 6 if target == 0: 7 res.append(track[:]) 8 return 9 for i in range(index, len(candidates)): 10 if target - candidates[i] < 0: # 超過目標和 11 break 12 if i > index and candidates[i] == candidates[i-1]: 13 continue 14 backtrack(i + 1, track + [candidates[i]], target - candidates[i]) 15 backtrack(0, [], target) 16 return res
####https://www.cnblogs.com/HMJIang/####
4、陣列元素不重復但可以重復使用
這一類的問題同樣也是第二種問題演變而來，唯一的區別是遞回呼叫backtrack的時候，把 i + 1 改成 i ，那么下一個位置又可以用這個元素了，即可實作有重復
Leetcode 39 組合總和
1 class Solution: 2 def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: 3 res = [] 4 candidates.sort() 5 def backtrack(index, track, target): 6 if target == 0: 7 res.append(track[:]) 8 return 9 for i in range(index, len(candidates)): 10 if target - candidates[i] < 0: 11 break 12 ###把原來遞回的時候 i+1 改成 i，當前的元素又可以再用一次了 13 backtrack(i, track + [candidates[i]], target - candidates[i]) 14 backtrack(0, [], target) 15 return res
####https://www.cnblogs.com/HMJIang/####
歡迎轉載，轉載請注明出處： https://www.cnblogs.com/HMJIang/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/598.html
標籤：其他
上一篇：2020面試Java要點