本博客的內(nèi)容只是做一個大概的記錄，整個PDF看下來，內(nèi)容上是不如代碼隨想錄網(wǎng)站上的文章全面的，并且PDF中有些地方的描述，是很讓我疑惑的，在困擾我很久后，無意間發(fā)現(xiàn)，其網(wǎng)站上的講解完全符合我的思路。這次看完這些PDF后，暫時一段時間內(nèi)不會再看了，要復(fù)習(xí)還是依靠，代碼隨想錄網(wǎng)站，視頻，和我自己寫的博客吧

回溯算法章節(jié)，這算是我掌握的還行的一個章節(jié)了。

組合

其中使用的剪枝技巧值得學(xué)習(xí)。

組合總和 III

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:self.res = []path = []idx = 1self.backtracking(k,n,idx,path)return self.resdef backtracking(self,k,n,idx,path):if len(path)==k :if n == 0 :self.res.append(path.copy())returnelse :return# 小小剪枝for i in range(idx,10-(k-len(path))+1):# 小小剪枝if n-i < 0 :continueelse :path.append(i)self.backtracking(k,n-i,i+1,path)path.pop()return 

電話號碼的字母組合

只要用 idx 來控制當前應(yīng)該取第幾個數(shù)字，就只需要一層循環(huán)了，而不是之前我習(xí)慣的兩層循環(huán)。

class Solution:def letterCombinations(self, digits: str) -> List[str]:if digits == '' :return []self.dict = {'1' : '', '0' : '' , '#' : '' , '*' : '' ,'2':'abc' , '3':'def' , '4':'ghi' , '5':'jkl', '6':'mno' ,'7':'pqrs','8':'tuv','9':'wxyz'}self.res = []path = []n = len(digits)idx = 0self.backtracking(digits,n,idx,path)return self.resdef backtracking(self,digits,n,idx,path):if len(path) == n :self.res.append(''.join(path))return# 取當前的數(shù)字number = digits[idx]ss = self.dict[number]m = len(ss)# 在當前數(shù)字對應(yīng)的字符串中，從0開始遍歷for i in range(m):path.append(ss[i])self.backtracking(digits,n,idx+1,path)path.pop()

組合總和

本題需要注意的是，雖然元素可以重復(fù)，但是必須要有idx，idx是保證，遍歷一直是正序的，不會走回頭路。

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:self.res = []path = []n = len(candidates)idx = 0self.backtracking(candidates,n,target,idx,path)return self.resdef backtracking(self,candidates,n,target,idx,path):if target == 0 :self.res.append(path.copy())returnif target < 0 :returnfor i in range(idx,n):if target < candidates[i] :continuepath.append(candidates[i])# 注意這里,傳入 idx 的區(qū)別,因為元素可以重復(fù)，所以是 i , 不是 i+1# 但是也必須要有idx !!! self.backtracking(candidates,n,target-candidates[i],i,path)path.pop()

本題，代碼隨想錄的剪枝策略是，排序之后加剪枝，可以，不符合條件直接跳出當層for循環(huán)了。

class Solution:def backtracking(self, candidates, target, total, startIndex, path, result):if total == target:result.append(path[:])returnfor i in range(startIndex, len(candidates)):if total + candidates[i] > target:breaktotal += candidates[i]path.append(candidates[i])self.backtracking(candidates, target, total, i, path, result)total -= candidates[i]path.pop()def combinationSum(self, candidates, target):result = []candidates.sort()  # 需要排序self.backtracking(candidates, target, 0, 0, [], result)return result

組合總和II

剪枝+used數(shù)組去重。

class Solution:def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:candidates.sort()n = len(candidates)self.res = []path = []used = [False]*nidx = 0self.backtracking(candidates,target,n,idx,path,used)return self.resdef backtracking(self,candidates,target,n,idx,path,used):if target == 0 :self.res.append(path.copy())returnif target < 0 :return for i in range(idx,n):if candidates[i] > target :breakif i > 0 and used[i-1] == False and candidates[i]==candidates[i-1]:continuepath.append(candidates[i])used[i] = Trueself.backtracking(candidates,target-candidates[i],n,i+1,path,used)used[i] = Falsepath.pop()

樹層去重，used[i-1] = False 。樹枝去重，used[i-1] = True .

代碼隨想錄的代碼

class Solution:def backtracking(self, candidates, target, total, startIndex, used, path, result):if total == target:result.append(path[:])returnfor i in range(startIndex, len(candidates)):# 對于相同的數(shù)字，只選擇第一個未被使用的數(shù)字，跳過其他相同數(shù)字if i > startIndex and candidates[i] == candidates[i - 1] and not used[i - 1]:continueif total + candidates[i] > target:breaktotal += candidates[i]path.append(candidates[i])used[i] = Trueself.backtracking(candidates, target, total, i + 1, used, path, result)used[i] = Falsetotal -= candidates[i]path.pop()def combinationSum2(self, candidates, target):used = [False] * len(candidates)result = []candidates.sort()self.backtracking(candidates, target, 0, 0, used, [], result)return result

分割回文串

注意分割區(qū)間定義即可，左閉右閉。

class Solution:def partition(self, s: str) -> List[List[str]]:self.res = []path = []n = len(s)idx = 0self.backtracking(s,n,idx,path)return self.resdef backtracking(self,s,n,idx,path):if idx >= n :self.res.append(path.copy())return # 這里注意細節(jié)就好，i就是要取到n-1# 加入s='aa',s[1:2]='a'，索引下標，是不包括最后一個值的for i in range(idx,n):# 注意回文子串區(qū)間定義：[idx,i],i為分割線temp = s[idx:i+1]if self.is_right(temp):path.append(temp)self.backtracking(s,n,i+1,path)path.pop()def is_right(self,temp):left = 0right = len(temp)-1while left < right :if temp[left]!=temp[right]:return Falseleft += 1right -= 1 return True

還可以提前使用動態(tài)規(guī)劃的方法，判斷出給字符串的所有子串是否是回文串，然后將結(jié)果儲存起來。核心代碼就是，先從下到上遍歷，再從左到右遍歷，一共需要考慮三種情況，會導(dǎo)致 dp[i][j] 是回文串，dp[i][j] 代表字符串中 [i,j] 的子串，是不是回文串。

class Solution:def partition(self, s: str) -> List[List[str]]:result = []isPalindrome = [[False] * len(s) for _ in range(len(s))]  # 初始化isPalindrome矩陣self.computePalindrome(s, isPalindrome)self.backtracking(s, 0, [], result, isPalindrome)return resultdef backtracking(self, s, startIndex, path, result, isPalindrome):if startIndex >= len(s):result.append(path[:])returnfor i in range(startIndex, len(s)):if isPalindrome[startIndex][i]:   # 是回文子串substring = s[startIndex:i + 1]path.append(substring)self.backtracking(s, i + 1, path, result, isPalindrome)  # 尋找i+1為起始位置的子串path.pop()           # 回溯過程，彈出本次已經(jīng)添加的子串def computePalindrome(self, s, isPalindrome):for i in range(len(s) - 1, -1, -1):  # 需要倒序計算，保證在i行時，i+1行已經(jīng)計算好了for j in range(i, len(s)):if j == i:isPalindrome[i][j] = Trueelif j - i == 1:isPalindrome[i][j] = (s[i] == s[j])else:isPalindrome[i][j] = (s[i] == s[j] and isPalindrome[i+1][j-1])

復(fù)原IP地址

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:self.res = []path = []idx = 0n = len(s)self.backtacking(s,n,idx,path)return self.resdef backtacking(self,s,n,idx,path):if idx >= n :if len(path)==4:self.res.append('.'.join(path))returnelse :returnif len(path)==3 :temp = s[idx:n]if self.is_right(temp):path.append(temp)self.backtacking(s,n,n,path)path.pop()else :for i in range(idx,n):  temp = s[idx:i+1]if self.is_right(temp):path.append(temp)self.backtacking(s,n,i+1,path)path.pop()def is_right(self,temp):n = len(temp)if temp[0] == '0' and n > 1 :return Falseif int(temp) > 255 or int(temp) < 0 :return Falsereturn True

我覺得我還剪了一下枝，挺好，

代碼隨想錄的代碼：

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:results = []self.backtracking(s, 0, [], results)return resultsdef backtracking(self, s, index, path, results):if index == len(s) and len(path) == 4:results.append('.'.join(path))returnif len(path) > 4:  # 剪枝returnfor i in range(index, min(index + 3, len(s))):if self.is_valid(s, index, i):sub = s[index:i+1]path.append(sub)self.backtracking(s, i+1, path, results)path.pop()def is_valid(self, s, start, end):if start > end:return Falseif s[start] == '0' and start != end:  # 0開頭的數(shù)字不合法return Falsenum = int(s[start:end+1])return 0 <= num <= 255

子集

冗余的代碼，本題不需要 used 數(shù)組，idx 已經(jīng)可以控制，不出現(xiàn)重復(fù)了。

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:self.res = []path = []n = len(nums)used = [False]*nidx = 0self.backtracking(nums,n,idx,used,path)return self.resdef backtracking(self,nums,n,idx,used,path):self.res.append(path.copy())# 本題還是要有idxfor i in range(idx,n):if used[i]==False :used[i]=Truepath.append(nums[i])self.backtracking(nums,n,i+1,used,path)path.pop()used[i]=False

求組合，就要用到 idx ，求排列，不需要 idx ， 而且本題不需要 used 數(shù)組，idx 已經(jīng)成功控制了。

代碼隨想錄的代碼：

class Solution:def subsets(self, nums):result = []path = []self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:])  # 收集子集，要放在終止添加的上面，否則會漏掉自己# if startIndex >= len(nums):  # 終止條件可以不加#     returnfor i in range(startIndex, len(nums)):path.append(nums[i])self.backtracking(nums, i + 1, path, result)path.pop()

子集II

直接套用之前的去重邏輯。

class Solution:def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:self.res = []path = []nums.sort()n = len(nums)used = [False]*nidx = 0self.backtracking(nums,n,idx,used,path)return self.resdef backtracking(self,nums,n,idx,used,path):self.res.append(path.copy())# 本題還是要有idxfor i in range(idx,n):if i > 0 and used[i-1]==False and nums[i-1]==nums[i]:continueelse:   used[i]=Truepath.append(nums[i])self.backtracking(nums,n,i+1,used,path)path.pop()used[i]=False

遞增子序列

本題太具有迷惑性了，一開始還真沒注意！本題給的示例都是排好序的，讓我誤以為可以使用之前的去重邏輯！實則不然，因為求的是遞增子序列，這意味著我們不能對數(shù)組進行排序操作，所以不能使用之前的去重邏輯。要使用新的，在遞歸函數(shù)中每次都聲明的，哈希(集合)去重邏輯，我不喜歡用set，我喜歡用哈希。

class Solution:def findSubsequences(self, nums: List[int]) -> List[List[int]]:self.res = []path = []idx = 0n = len(nums)self.backtracking(nums,n,idx,path)return self.resdef backtracking(self,nums,n,idx,path):if len(path)>=2:self.res.append(path.copy())used = [False]*201for i in range(idx,n):if used[100+nums[i]] == True:continueif path==[] or nums[i] >= path[-1] :path.append(nums[i])used[100+nums[i]] = Trueself.backtracking(nums,n,i+1,path)path.pop()

代碼隨想錄的代碼

遞增子序列

class Solution:def findSubsequences(self, nums):result = []path = []self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):if len(path) > 1:result.append(path[:])  # 注意要使用切片將當前路徑的副本加入結(jié)果集# 注意這里不要加return，要取樹上的節(jié)點uset = set()  # 使用集合對本層元素進行去重for i in range(startIndex, len(nums)):if (path and nums[i] < path[-1]) or nums[i] in uset:continueuset.add(nums[i])  # 記錄這個元素在本層用過了，本層后面不能再用了path.append(nums[i])self.backtracking(nums, i + 1, path, result)path.pop()

class Solution:def findSubsequences(self, nums):result = []path = []self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):if len(path) > 1:result.append(path[:])  # 注意要使用切片將當前路徑的副本加入結(jié)果集used = [0] * 201  # 使用數(shù)組來進行去重操作，題目說數(shù)值范圍[-100, 100]for i in range(startIndex, len(nums)):if (path and nums[i] < path[-1]) or used[nums[i] + 100] == 1:continue  # 如果當前元素小于上一個元素，或者已經(jīng)使用過當前元素，則跳過當前元素used[nums[i] + 100] = 1  # 標記當前元素已經(jīng)使用過path.append(nums[i])  # 將當前元素加入當前遞增子序列self.backtracking(nums, i + 1, path, result)path.pop()

全排列

求排列，不需要 idx , 遞歸中每次都是從0開始遍歷，但要用used數(shù)組，來表示哪些元素已經(jīng)被使用過。

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:self.res = []path = []n = len(nums)used = [False]*nself.backtracking(nums,n,used,path)return self.resdef backtracking(self,nums,n,used,path):if len(path)==n:self.res.append(path.copy())returnfor i in range(n):if used[i]==False :used[i]=Truepath.append(nums[i])self.backtracking(nums,n,used,path)path.pop()used[i]=False

全排列 II

小小去重，可笑可笑

lass Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:self.res = []path = []n = len(nums)nums.sort()used = [False]*nself.backtracking(nums,n,used,path)return self.resdef backtracking(self,nums,n,used,path):if len(path)==n:self.res.append(path.copy())returnfor i in range(n):if i > 0 and used[i-1] == False and nums[i-1]==nums[i]:continueif used[i]==False:used[i]=Truepath.append(nums[i])self.backtracking(nums,n,used,path)path.pop()used[i]=False

但是這道題的去重很有意思，要去看代碼隨想錄的解答。

全排列 II

回溯算法去重問題的另一種寫法

可以看看，核心思想是，講解樹層去重和樹枝去重。

回溯算法去重問題的另一種寫法

重新安排行程

再看依舊是不會

重新安排行程

class Solution:def findItinerary(self, tickets: List[List[str]]) -> List[str]:tickets.sort() # 先排序，這樣一旦找到第一個可行路徑，一定是字母排序最小的used = [0] * len(tickets)path = ['JFK']results = []self.backtracking(tickets, used, path, 'JFK', results)return results[0]def backtracking(self, tickets, used, path, cur, results):if len(path) == len(tickets) + 1:  # 終止條件：路徑長度等于機票數(shù)量+1results.append(path[:])  # 將當前路徑添加到結(jié)果列表return Truefor i, ticket in enumerate(tickets):  # 遍歷機票列表if ticket[0] == cur and used[i] == 0:  # 找到起始機場為cur且未使用過的機票used[i] = 1  # 標記該機票為已使用path.append(ticket[1])  # 將到達機場添加到路徑中state = self.backtracking(tickets, used, path, ticket[1], results)  # 遞歸搜索path.pop()  # 回溯，移除最后添加的到達機場used[i] = 0  # 標記該機票為未使用if state:return True  # 只要找到一個可行路徑就返回，不繼續(xù)搜索

from collections import defaultdictclass Solution:def findItinerary(self, tickets: List[List[str]]) -> List[str]:targets = defaultdict(list)  # 構(gòu)建機場字典for ticket in tickets:targets[ticket[0]].append(ticket[1])for airport in targets:targets[airport].sort()  # 對目的地列表進行排序path = ["JFK"]  # 起始機場為"JFK"self.backtracking(targets, path, len(tickets))return pathdef backtracking(self, targets, path, ticketNum):if len(path) == ticketNum + 1:return True  # 找到有效行程airport = path[-1]  # 當前機場destinations = targets[airport]  # 當前機場可以到達的目的地列表for i, dest in enumerate(destinations):targets[airport].pop(i)  # 標記已使用的機票path.append(dest)  # 添加目的地到路徑if self.backtracking(targets, path, ticketNum):return True  # 找到有效行程targets[airport].insert(i, dest)  # 回溯，恢復(fù)機票path.pop()  # 移除目的地return False  # 沒有找到有效行程

N皇后

前幾天寫過了，核心思想就是，皇后一定是一行一行放的，每行放一個，所以可以用一個idx來控制當前是第幾行，只要for循環(huán)遍歷每個列位置就可以了，另外，在判斷皇后是否合法時，我們只需要知道每個皇后的位置就可以了，不需要傳入整個棋盤，那樣太復(fù)雜了。

代碼隨想錄的代碼：

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:result = []  # 存儲最終結(jié)果的二維字符串數(shù)組chessboard = ['.' * n for _ in range(n)]  # 初始化棋盤self.backtracking(n, 0, chessboard, result)  # 回溯求解return [[''.join(row) for row in solution] for solution in result]  # 返回結(jié)果集def backtracking(self, n: int, row: int, chessboard: List[str], result: List[List[str]]) -> None:if row == n:result.append(chessboard[:])  # 棋盤填滿，將當前解加入結(jié)果集returnfor col in range(n):if self.isValid(row, col, chessboard):chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:]  # 放置皇后self.backtracking(n, row + 1, chessboard, result)  # 遞歸到下一行chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:]  # 回溯，撤銷當前位置的皇后def isValid(self, row: int, col: int, chessboard: List[str]) -> bool:# 檢查列for i in range(row):if chessboard[i][col] == 'Q':return False  # 當前列已經(jīng)存在皇后，不合法# 檢查 45 度角是否有皇后i, j = row - 1, col - 1while i >= 0 and j >= 0:if chessboard[i][j] == 'Q':return False  # 左上方向已經(jīng)存在皇后，不合法i -= 1j -= 1# 檢查 135 度角是否有皇后i, j = row - 1, col + 1while i >= 0 and j < len(chessboard):if chessboard[i][j] == 'Q':return False  # 右上方向已經(jīng)存在皇后，不合法i -= 1j += 1return True  # 當前位置合法

數(shù)獨

本題的要點在于，就是在每個遞歸函數(shù)中，都使用三層，從0開始遍歷的for循環(huán)，遍歷行，遍歷列，遍歷數(shù)字，利用棋盤中，該位置是否是空，來判斷是否在該位置填入數(shù)字，這樣的編程邏輯是非常自然的。如果是想用idx來控制當前輸入到了第幾行第幾列，那樣就太麻煩了！遇到數(shù)字就continue，多跑幾次什么都不做的for循環(huán)是無所謂的！

同樣，在上面的編寫邏輯下，判斷是否合法也是較為容易的，只需要傳入當前參數(shù)，每層循環(huán)的 i j k ，去判斷，同行，同列，同小塊，是否合法即可。

代碼隨想錄的代碼：

class Solution:def solveSudoku(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""self.backtracking(board)def backtracking(self, board: List[List[str]]) -> bool:# 若有解，返回True；若無解，返回Falsefor i in range(len(board)): # 遍歷行for j in range(len(board[0])):  # 遍歷列# 若空格內(nèi)已有數(shù)字，跳過if board[i][j] != '.': continuefor k in range(1, 10):if self.is_valid(i, j, k, board):board[i][j] = str(k)if self.backtracking(board): return Trueboard[i][j] = '.'# 若數(shù)字1-9都不能成功填入空格，返回False無解return Falsereturn True # 有解def is_valid(self, row: int, col: int, val: int, board: List[List[str]]) -> bool:# 判斷同一行是否沖突for i in range(9):if board[row][i] == str(val):return False# 判斷同一列是否沖突for j in range(9):if board[j][col] == str(val):return False# 判斷同一九宮格是否有沖突start_row = (row // 3) * 3start_col = (col // 3) * 3for i in range(start_row, start_row + 3):for j in range(start_col, start_col + 3):if board[i][j] == str(val):return Falsereturn True