回溯法
回溯法的基本思想
回溯法本质上是一种系统性地搜索问题解空间的方法。它通过尝试各种可能的解决方案,并在发现当前路径不可行时"回溯"到之前的状态,继续探索其他可能性。这个过程实际上就是在搜索所有可能的解决方案。
牛刀小試
程式碼範例
Leetcode 40. 组合总和 II
python
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(index, remaining, current):
if remaining == 0:
ans.append(current[:])
return
for i in range(index, len(candidates)):
if i > index and candidates[i] == candidates[i - 1]:
continue
if candidates[i] > remaining:
break
current.append(candidates[i])
backtrack(i + 1, remaining - candidates[i], current)
current.pop()
ans = []
candidates.sort()
backtrack(0, target, [])
return ans程式碼解釋
python
def backtrack(index, remaining, current):定義一個內部的backtrack函數,用於回溯搜索。它接受三個參數:index(當前考慮的候選數字索引),remaining(剩餘需要達到的和),current(當前組合)。
python
if remaining == 0:
ans.append(current[:])
return如果剩餘和為0,表示找到一個有效組合,將其添加到答案列表中並返回。
python
if i > index and candidates[i] == candidates[i - 1]:
continue跳過重複的數字,以避免重複組合。
python
if candidates[i] > remaining:
break如果當前數字大於剩餘和,由於數組已排序,後面的數字也會更大,因此可以直接退出循環。
python
current.append(candidates[i])
backtrack(i + 1, remaining - candidates[i], current)
current.pop()將當前數字添加到組合中,遞歸調用backtrack函數,然後移除該數字以嘗試下一種可能。
初始化答案列表,對候選數字排序,調用backtrack函數開始搜索,最後返回答案。****
Contributors
lucashsu95