一、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))