概述

其實回溯算法和我們常説的 DFS 算法非常類似，本質上就是一種暴力窮舉算法。回溯算法和 DFS 算法的細微差別是：回溯算法是在遍歷「樹枝」，DFS 算法是在遍歷「節點」

抽象地説，解決一個回溯問題，實際上就是遍歷一棵決策樹的過程，樹的每個葉子節點存放着一個合法答案。你把整棵樹遍歷一遍，把葉子節點上的答案都收集起來，就能得到所有的合法答案。

站在回溯樹的一個節點上，你只需要思考 3 個問題：

1、路徑：也就是已經做出的選擇。

2、選擇列表：也就是你當前可以做的選擇。

3、結束條件：也就是到達決策樹底層，無法再做選擇的條件。

代碼方面，回溯算法的框架：

result = []
def backtrack(路徑, 選擇列表):
    if 滿足結束條件:
        result.add(路徑)
        return
    
    for 選擇 in 選擇列表:
        做選擇
        backtrack(路徑, 選擇列表)
        撤銷選擇

for循環就是遍歷集合區間，可以理解一個節點有多少個孩子，這個for循環就執行多少次。

backtracking這裏自己調用自己，實現遞歸。

其核心就是 for 循環裏面的遞歸，在遞歸調用之前「做選擇」，在遞歸調用之後「撤銷選擇」

回溯算法解決組合問題

這裏的組合問題 元素無重不可複選

class Solution {

    List<List<Integer>> res = new LinkedList<>();
    // 記錄回溯算法的遞歸路徑
    LinkedList<Integer> track = new LinkedList<>();

    // 主函數
    public List<List<Integer>> combine(int n, int k) {
        backtrack(1, n, k);
        return res;
    }

    void backtrack(int start, int n, int k) {
        // base case
        if (k == track.size()) {
            // 遍歷到了第 k 層，收集當前節點的值
            res.add(new LinkedList<>(track));
            return;
        }
        
        // 回溯算法標準框架
        for (int i = start; i <= n; i++) {
            // 選擇
            track.addLast(i);
            // 通過 start 參數控制樹枝的遍歷，避免產生重複的子集
            backtrack(i + 1, n, k);
            // 撤銷選擇
            track.removeLast();
        }
    }
}

回溯算法解決排列問題

class Solution {

    List<List<Integer>> res = new LinkedList<>();
    // 記錄回溯算法的遞歸路徑
    LinkedList<Integer> track = new LinkedList<>();
    // track 中的元素會被標記為 true
    boolean[] used;

    /* 主函數，輸入一組不重複的數字，返回它們的全排列 */
    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backtrack(nums);
        return res;
    }

    // 回溯算法核心函數
    void backtrack(int[] nums) {
        // base case，到達葉子節點
        if (track.size() == nums.length) {
            // 收集葉子節點上的值
            res.add(new LinkedList(track));
            return;
        }

        // 回溯算法標準框架
        for (int i = 0; i < nums.length; i++) {
            // 已經存在 track 中的元素，不能重複選擇
            if (used[i]) {
                continue;
            }
            // 做選擇
            used[i] = true;
            track.addLast(nums[i]);
            // 進入下一層回溯樹
            backtrack(nums);
            // 取消選擇
            track.removeLast();
            used[i] = false;
        }
    }
}

總結

回溯算法就是個多叉樹的遍歷問題，關鍵就是在前序遍歷和後序遍歷的位置做一些操作，算法框架如下：

def backtrack(...):
    for 選擇 in 選擇列表:
        做選擇
        backtrack(...)
        撤銷選擇

寫 backtrack 函數時，需要維護走過的「路徑」和當前可以做的「選擇列表」，當觸發「結束條件」時，將「路徑」記入結果集。