力扣hot100_回溯(2)_python版本

一、39. 组合总和（中等）

• 代码：

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:ans = []path = []def dfs(i: int, left: int) -> None:if left == 0:# 找到一个合法组合ans.append(path.copy())returnif i == len(candidates) or left < 0:return# 不选dfs(i + 1, left)# 选path.append(candidates[i])dfs(i, left - candidates[i])path.pop()  # 恢复现场dfs(0, target)return ans

二、22. 括号生成

• 代码

class Solution:def generateParenthesis(self, n: int) -> List[str]:m = n * 2  # 括号长度ans = []path = [''] * m  # 所有括号长度都是一样的 m# i = 目前填了多少个括号# open = 左括号个数，i-open = 右括号个数def dfs(i: int, open: int) -> None:if i == m:  # 括号构造完毕ans.append(''.join(path))  # 加入答案returnif open < n:  # 可以填左括号path[i] = '('  # 直接覆盖dfs(i + 1, open + 1)  # 多了一个左括号if i - open < open:  # 可以填右括号path[i] = ')'  # 直接覆盖dfs(i + 1, open)dfs(0, 0)return ans

三、79. 单词搜索（中等）

• 代码

class Solution:def exist(self, board: List[List[str]], word: str) -> bool:m, n = len(board), len(board[0])def dfs(i: int, j: int, k: int) -> bool:if board[i][j] != word[k]:  # 匹配失败return Falseif k == len(word) - 1:  # 匹配成功！return Trueboard[i][j] = ''  # 标记访问过for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):  # 相邻格子if 0 <= x < m and 0 <= y < n and dfs(x, y, k + 1):return True  # 搜到了！board[i][j] = word[k]  # 恢复现场return False  # 没搜到return any(dfs(i, j, 0) for i in range(m) for j in range(n))