演算法筆記：Backtracking

什麼是 Backtracking？

Backtracking 中文直翻叫「回溯」，在演算法中是一種搜尋方法。

其核心思想為： 嘗試一條路徑，若發現不符合條件，則回溯，然後嘗試其他可能性。

可以將其想像成一種 DFS 的延伸， 但相較於 DFS，Backtracking 會找出「所有」、「可能」的解，並透過提早刪除不可能的路徑來提高效率。(當然，DFS 也能寫複雜一點做到這些，但在描述 DFS 演算法時，我們並不預設它需要寫得如 Backtracking 複雜)。

什麼情況下我該想到 Backtracking？

• 找出所有可能、路徑、解法

• 每一步都需做出選擇（如選哪個數、放在哪個位置）

• 解的過程為試錯，需要回退到前一個狀態

如果有上面特徵、外加有明確的限制時，就要提早刪除不可能的路徑。

核心架構與實作

1. 定義每一個步驟的選擇

2. 列出當下所有可能選擇

3. 終止條件

4. 回溯

5. 提早刪除不可能的路徑
   不是必須，但需要提升效能時可以優先從這裡著手

這邊以「Leetcode 46: Permutations」以 C++ 實作為例，說明上面架構。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> gNums;
    int gNumsLen;
    vector<vector<int>> permute(vector<int>& nums) {
        if (nums.size() == 1) {
            result.push_back(nums);
            return result;
        }

        gNums = nums;
        gNumsLen = nums.size();
        vector<bool> mark(nums.size(), false);
        vector<int> subSet;

        findPermute(mark, subSet);
        return result;
    }

    void findPermute(vector<bool>& mark, vector<int>& subSet) {
        if (gNumsLen == subSet.size()) { // 終止條件
            result.push_back(subSet);
            return;
        }

        for (int i=0; i<gNumsLen; i++) { // 列出所有可能
            if (mark[i]) continue; // 提早刪除不可能的路徑

            mark[i] = true;             // 做出選擇
            subSet.push_back(gNums[i]); // 做出選擇
            findPermute(mark, subSet);  // 遞迴探索下一步

            subSet.pop_back();  // 回溯(撤銷選擇)
            mark[i] = false;    // 回溯(撤銷選擇)
        }
    }
};

整體來說就是：先做選擇 → 遞迴探索 → 撤銷選擇，每達到一次終止條件(=找到一個解)時，便將解儲存起來。 

常用情境與練習

• 排列
  備註：以 C++ 來說，有 next_permutation、prev_permutation 等 _permutation 工具，不一定要自己實作出來。
  通常會搭配一個 used[] 紀錄使用情況。

  •  Leetcode 46: Permutations
  •  Leetcode 47: Permutations II

• 組合

  • Leetcode 77: Combinations
  • Leetcode 39: Combination Sum
  • Leetcode 40: Combination Sum II
  • Leetcode 216: Combination Sum III

• 子集合

  • Leetcode 78: Subsets
  • Leetcode 90: Subsets II

• 棋盤問題(八皇后)

  • Leetcode 51: N-Queens
  • Leetcode 52: N-Queens II
  • Leetcode 34: Find First and Last Position of Element in Sorted Array

• 路徑搜尋

  • Leetcode 79: Word Search
  • Leetcode 212: Word Search II

 

 

總結來說，Backtracking 是透過「嘗試 → 檢查 → 回溯」探索所有可能解的搜尋方法，可以透過提早刪除不可能選項來減少不必要的計算。

它廣泛應用於排列組合、子集合、棋盤與路徑搜尋等問題，熟悉它的核心架構與應用模式，能在面對各式演算法題時更加得心應手。