回溯算法理論基礎

https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
回溯法也可以叫做回溯搜索法，它是一種搜索的方式。
回溯是遞歸的副產品，只要有遞歸就會有回溯。
回溯法并不是什么高效的算法 =>本質是窮舉，窮舉所有可能，然后選出我們想要的答案，如果想讓回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是窮舉的本質。
回溯法，一般可以解決如下幾種問題：

• 組合問題：N個數里面按一定規則找出k個數的集合
• 切割問題：一個字符串按一定規則有幾種切割方式
• 子集問題：一個N個數的集合里有多少符合條件的子集
• 排列問題：N個數按一定規則全排列，有幾種排列方式
• 棋盤問題：N皇后，解數獨等等
  所有回溯法的問題都可以抽象為樹形結構

回溯三部曲

• 回溯函數模板返回值以及參數 - backtracking
• 回溯函數終止條件 - 搜到葉子節點了，也就找到了滿足條件的一條答案，把這個答案存放起來，并結束本層遞歸

  if (終止條件) {存放結果;return;
  }
  

• 回溯搜索的遍歷過程 - 集合的大小構成了樹的寬度，遞歸的深度構成的樹的深度。

  for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {處理節點;backtracking(路徑，選擇列表); // 遞歸回溯，撤銷處理結果
  }
  

for循環就是遍歷集合區間，可以理解一個節點有多少個孩子，這個for循環就執行多少次。
backtracking這里自己調用自己，實現遞歸。
大家可以從圖中看出for循環可以理解是橫向遍歷，backtracking（遞歸）就是縱向遍歷，這樣就把這棵樹全遍歷完了，一般來說，搜索葉子節點就是找的其中一個結果了。
![[Pasted image 20240301152922.png]]
完整模板：

void backtracking(參數) {if (終止條件) {存放結果;return;}for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {處理節點;backtracking(路徑，選擇列表); // 遞歸回溯，撤銷處理結果}
}

77.組合

https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:result = []self.backtracking(n,k,1,[],result)return resultdef backtracking(self, n, k, startIndex, path, result):if len(path) == k:result.append(path[:])returnfor i in range(startIndex, n+1):path.append(i)self.backtracking(n,k,i+1,path,result)path.pop()