回溯基礎概念

什么是回溯？

如何實現回溯？

第77題. 組合

題目

思路與解法

carl的講解： 回溯搜索法

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:self.path = []self.res = []self.backtracking(n, k, 1)return self.resdef backtracking(self, n, k, startIdx):if len(self.path) == k:self.res.append(self.path[:]) # 遍歷path里面的值再存入res中，不然存入的是path的引用，這樣存入res中的值就會跟著path變了print(self.path)returnif startIdx > n:returni = startIdxwhile i <= n:self.path.append(i)self.backtracking(n, k, i + 1)self.path.pop()i += 1

216. 組合總和 III

題目

思路與解法

第一想法： 很類似于上一道題，只是終止條件不一樣

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:self.path = []self.sum = 0self.res = []self.backtracking(k, n, 1)return self.resdef backtracking(self, k, n, startIdx):if self.sum == n and len(self.path) == k:self.res.append(self.path[:])returnif len(self.path) > k or self.sum > n or startIdx > 9:returni = startIdxwhile i < 10:self.path.append(i)self.sum += iself.backtracking(k, n, i+1)self.path.pop()self.sum -= ii += 1

17. 電話號碼的字母組合

題目

思路與解法

第一想法： 先用字典存入數字和字母的對應關系，然后使用回溯法遍歷每個字母段。遞歸的退出條件是當前取字母的地方是最后一個字母段。

class Solution:def letterCombinations(self, digits: str) -> List[str]:if not digits:return []self.dig2char = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}self.chars = []self.res = []self.path = []for item in digits:self.chars.append(self.dig2char.get(item))self.backtracking(0)return self.resdef backtracking(self,starIdx):if starIdx >= len(self.chars):self.res.append("".join(self.path))returnchars = self.chars[starIdx]for char in chars:self.path.append(char)self.backtracking(starIdx + 1)self.path.pop()