🔙 Backtracking

系統化窮舉——選擇、遞迴、撤銷。

19 題

📖 分類導讀

回溯法是一種系統性地搜尋所有可能解的演算法。透過「選擇、探索、撤銷」三步驟，在搜尋樹上進行深度優先搜尋。

Notes:

  • 回溯的核心模板：做選擇 → 遞迴 → 撤銷選擇
  • 剪枝 (Pruning) 是提升效率的關鍵
  • 排列 vs 組合 vs 子集，三種變體的差異要掌握

狀態空間樹

把回溯想成在一棵狀態空間樹上做 DFS：每個節點是一個「部分解」，每條邊是「一個決策」，葉子是「完整解或走不通的死路」。回溯 = 沿著樹往下探索，走不通就退回上一個決策點，換另一條邊再試——這就是「撤銷選擇」的意義。

fun <T> backtrack(state: MutableList<T>, choices: List<T>, res: MutableList<List<T>>) {
    if (isComplete(state)) {            // 終止條件：收集一個解
        res.add(ArrayList(state))
        return
    }
    for (choice in choices) {
        if (!isValid(state, choice)) continue   // 剪枝：跳過不合法分支
        state.add(choice)               // 做選擇
        backtrack(state, choices, res)  // 探索
        state.removeAt(state.size - 1)  // 撤銷選擇
    }
}

複雜度與剪枝

時間複雜度約為 O(分支數 ^ 深度)——子集約 O(2^n)、排列約 O(n!)。因為基底是指數，剪枝（提早砍掉不可能產生解的分支）往往是能否在時限內跑完的關鍵。

TIP

「搜尋問題的本質是圖/樹遍歷」：把合法狀態當節點、合法決策當邊，從起始狀態走到目標狀態的路徑就是解。看懂這層，回溯、DFS、甚至 BFS 求最短步數，其實是同一套搜尋框架的不同走法。

三種變體

  • 子集 (subsets)：每個元素「選或不選」，不在意順序。
  • 組合 (combinations)：選出 k 個、不計順序，用起始索引避免重複。
  • 排列 (permutations)：在意順序，用 used[] 標記已用元素。

跨倉庫導讀

#17Letter Combinations of a Phone NumberMedium★★★★★⏱ O(4^n * n)#39Combination SumMedium★★★★★#40Combination Sum IIMedium★★★★★⏱ O(2^n)#46PermutationsMedium★★★★★⏱ O(n * n!)#47Permutations IIMedium★★★★★⏱ O(n! * n)#51N-QueensHard★★★★★⏱ O(n!)#52N Queens IIHard★★★★★⏱ O(n!)#77CombinationsMedium★★★★★⏱ O(C(n,k) * k)#78SubsetsMedium★★★★★⏱ O(n * 2^n)#79Word SearchMedium★★★★★⏱ O(m * n * 4^L)#90Subsets IIMedium★★★★★⏱ O(n * 2^n)#93Restore IP AddressesMedium★★★★★⏱ O(3^4)#131Palindrome PartitioningMedium★★★★★⏱ O(n^2 + 2^n)#140Word Break IIHard★★★★★⏱ O(n² + total output)#473Matchsticks to SquareMedium★★★★★⏱ O(4^n)#698Partition to K Equal Sum SubsetsMedium★★★★★⏱ O(n * 2^n)#1239Maximum Length of a Concatenated String With Unique CharactersMedium★★★★★⏱ O(2^n)#1849Splitting a String Into Descending Consecutive ValuesMedium★★★★★⏱ O(n^2)#1980Find Unique Binary StringMedium★★★★★⏱ O(n)