理論基礎

• 回溯是一種純暴力搜索的方法，它和遞歸相輔相成，通常是執行完遞歸之后緊接著執行回溯
• 相較于以往使用的for循環暴力搜索，回溯能解決更為復雜的問題，如以下的應用場景
• 應用場景
  • 組合問題
    • 如一個集合{1,2,3,4}，找出長度為2的組合
  • 排列問題
    • 相較于組合，排列是有順序的，如{1,2}只有一種組合，但是有兩種排列
  • 切割問題
    • 給一個字符串，給一個要求，求得怎么切割滿足要求
  • 子集問題
    • 給一個集合，求它的子集
  • 棋盤問題
    • 如N皇后和解數獨等
• 回溯法的思維結構——樹型結構
  • 寬度代表集合的大小
  • 深度代表遞歸的深度
  • 

# 回溯編程模板
def backtracking(形參): # 返回值通常為空if (終止條件):存放結果returnfor (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）):處理節點backtracking(路徑，選擇列表) # 遞歸回溯，撤銷處理結果

*77. 組合

題目鏈接/文章講解：https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html
視頻講解：https://www.bilibili.com/video/BV1ti4y1L7cv
剪枝操作：https://www.bilibili.com/video/BV1wi4y157er

• 考點
  • 回溯
• 我的思路
  • 思路不到位
• 視頻講解關鍵點總結
  • 回溯（遞歸）三要素
    • 形參：當前值，上限值，組合大小，單個組合變量，總組合結果變量；返回值為空
    • 退出條件：單個組合變量的大小等于組合大小，此時將單個組合變量加入總組合結果變量，并返回
    • 回溯邏輯
      • 不斷地在范圍內循環遞歸求取單個組合變量
      • 循環范圍為當前值到上限值，每輪循環里：
        • 將當前值加入單個組合變量
        • 將當前值+1并遞歸
        • 執行回溯，即把單個組合變量里的最后一個值彈出，之后繼續下一輪循環
    • 剪枝優化
      • 回溯題常常可以在循環范圍上做優化
      • 本題可以把循環上限設置為上限值-（目標組合大小-當前組合大小）+2，+2是因為range函數在遍歷時不包括右邊界，所以要留出空余
• 我的思路的問題
  • 無思路
• 代碼書寫問題
  • 當想result變量添加單個組合變量時，要利用切片操作創建一個單個組合變量的副本并將該副本加入result，這是因為直接加入將僅僅把引用傳入到result里，后續的改動將導致result里的同步改動
• 可執行代碼

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