[algorithms] Backtracking 回溯法

視覺化概覽

graph TD
    R["[ ] 根節點"] --> A["[1]"]
    R --> B["[2]"]
    R --> C["[3]"]
    A --> A1["[1,2]"]
    A --> A2["[1,3]"]
    B --> B1["[2,1]"]
    B --> B2["[2,3]"]
    C --> C1["[3,1]"]
    C --> C2["[3,2]"]
    A1 --> A1a["[1,2,3] ✓"]
    A2 --> A2a["[1,3,2] ✓"]
    B1 --> B1a["[2,1,3] ✓"]
    B2 --> B2a["[2,3,1] ✓"]
    C1 --> C1a["[3,1,2] ✓"]
    C2 --> C2a["[3,2,1] ✓"]

    style A1a fill:#90EE90
    style A2a fill:#90EE90
    style B1a fill:#90EE90
    style B2a fill:#90EE90
    style C1a fill:#90EE90
    style C2a fill:#90EE90

什麼是回溯法？

回溯法是一種通過「嘗試所有可能」來找出所有解的演算法。當發現當前路徑不可能產生解時，就「回退」到上一步，嘗試其他選擇。

決策樹示例（全排列 [1,2,3]）：
                    []
           /        |        \
         [1]       [2]       [3]
        /   \     /   \     /   \
     [1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
      |      |     |     |     |      |
   [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

回溯法模板

void backtrack(路徑, 選擇列表) {
    if (滿足結束條件) {
        result.add(路徑);
        return;
    }
 
    for (選擇 : 選擇列表) {
        // 剪枝（可選）
        if (!isValid(選擇)) continue;
 
        做選擇;           // path.add(選擇)
        backtrack(路徑, 選擇列表);
        撤銷選擇;         // path.remove(...)
    }
}

經典問題

排列 vs 組合 vs 子集

問題	順序重要？	去重方式
排列	是	used[] 陣列
組合	否	start 參數
子集	否	start 參數

排列

void permute(int[] nums, boolean[] used, List<Integer> path) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        permute(nums, used, path);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

組合

void combine(int n, int k, int start, List<Integer> path) {
    if (path.size() == k) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i <= n - (k - path.size()) + 1; i++) { // 剪枝
        path.add(i);
        combine(n, k, i + 1, path);
        path.remove(path.size() - 1);
    }
}

子集

void subsets(int[] nums, int start, List<Integer> path) {
    result.add(new ArrayList<>(path)); // 每個節點都是答案
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        subsets(nums, i + 1, path);
        path.remove(path.size() - 1);
    }
}

剪枝技巧

不剪枝：遍歷整棵樹
     [root]
    / | \  \
   1  2  3  4   ← 全部展開

剪枝：提前終止不可能的分支
     [root]
    / |  ✂
   1  2       ← 3, 4 被剪掉

常見剪枝：

1. 排序 + 跳過 - 排序後相同元素跳過
2. 餘量不足 - 剩餘元素不夠組成解
3. 超過限制 - 當前和已超過目標

N 皇后問題

4 皇后的一個解：
. Q . .
. . . Q
Q . . .
. . Q .

檢查衝突：同列、對角線
queens[row] = col
同列：queens[i] == col
對角線：|queens[i] - col| == |i - row|

時間複雜度

問題	時間複雜度
全排列	O(n!)
組合 C(n,k)	O(C(n,k))
子集	O(2^n)
N 皇后	O(n!)

經典題目

1. 全排列 - LeetCode 46
2. 全排列 II（有重複） - LeetCode 47
3. 組合 - LeetCode 77
4. 組合總和 - LeetCode 39
5. 子集 - LeetCode 78
6. N 皇后 - LeetCode 51
7. 解數獨 - LeetCode 37
8. 單詞搜索 - LeetCode 79
9. 括號生成 - LeetCode 22
10. 復原 IP 地址 - LeetCode 93

相關檔案

• Java 實作：Backtracking.java