在這篇文章，我不僅會具體介紹之前沒有講到的回溯算法寫法，還會告訴你為什么可以那樣寫，兩種寫法的本質區別是什么。

先說結論：

1、回溯算法窮舉的本質思維模式是「球盒模型」，一切回溯算法，皆從此出，別無二法。

2、球盒模型，必然有兩種窮舉視角，分別為「球」的視角窮舉和「盒」的視角窮舉，對應的，就是兩種不同的代碼寫法。

3、從理論上分析，兩種窮舉視角本質上是一樣的。但是涉及到具體的代碼實現，兩種寫法的復雜度可能有優劣之分。你需要選擇效率更高的寫法。

球盒模型這個詞是我隨口編的，因為下面我會用「球」和「盒」兩種視角來解釋，你理解就好。

暴力窮舉思維方法：球盒模型

一切暴力窮舉算法，都從球盒模型開始，沒有例外。

你懂了這個，就可以隨心所欲運用暴力窮舉算法，下面的內容，請你仔細看，認真想。

首先，我們回顧一下以前學過的排列組合知識：

1、P(n, k)（也有很多書寫成A(n, k)）表示從n個不同元素中拿出k個元素的排列（Permutation/Arrangement）總數；C(n, k)表示從n個不同元素中拿出k個元素的組合（Combination）總數。

2、「排列」和「組合」的主要區別在于是否考慮順序的差異。

3、排列、組合總數的計算公式：

圖片

好，現在我問一個問題，這個排列公式P(n, k)是如何推導出來的？為了搞清楚這個問題，我需要講一點組合數學的知識。

排列組合問題的各種變體都可以抽象成「球盒模型」，P(n, k)就可以抽象成下面這個場景：

圖片

即，將n個標記了不同序號的球（標號為了體現順序的差異），放入k個標記了不同序號的盒子中（其中n >= k，每個盒子最終都裝有恰好一個球），共有P(n, k)種不同的方法。

現在你來，往盒子里放球，你怎么放？其實有兩種視角。

首先，你可以站在盒子的視角，每個盒子必然要選擇一個球。

這樣，第一個盒子可以選擇n個球中的任意一個，然后你需要讓剩下k - 1個盒子在n - 1個球中選擇：

圖片

另外，你也可以站在球的視角，因為并不是每個球都會被裝進盒子，所以球的視角分兩種情況：

1、第一個球可以不裝進任何一個盒子，這樣的話你就需要將剩下n - 1個球放入k個盒子。

2、第一個球可以裝進k個盒子中的任意一個，這樣的話你就需要將剩下n - 1個球放入k - 1個盒子。

結合上述兩種情況，可以得到：

圖片

你看，兩種視角得到兩個不同的遞歸式，但這兩個遞歸式解開的結果都是我們熟知的階乘形式：

圖片

至于如何解遞歸式，涉及數學的內容比較多，這里就不做深入探討了，有興趣的讀者可以自行學習組合數學相關知識。

用球盒模型重新理解全排列問題

好，上面從數學的角度介紹了全排列窮舉的兩種視角，現在回歸到代碼上，我要考你了哦。

前文 回溯算法核心框架 和 回溯算法秒殺排列/組合/子集的九種變體 都給出過全排列的代碼。

就以最基本的元素無重不可復選的全排列為例，我直接把代碼 copy 過來：

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;
        }
    }
}

請問，這個解法是以什么視角進行窮舉的？是以球的視角還是盒的視角？給你三分鐘思考，請回答！

這個代碼是以盒的視角進行窮舉的，即站在每個位置的角度來選擇球，站在nums中的每個索引，來選擇不同的元素放入這個索引位置。

為什么是這個答案呢？假設nums里面有n個數字，那么全排列問題相當于把n個球放到包含n個位置的盒子里，要求盒子必須裝滿，問你有幾種不同的裝法。

以盒的視角理解，盒子的第一個位置可以接收n個球的任意一個，有n種選擇，第二個位置可以接收n - 1個球的任意一個，有n - 1種選擇，第三個位置有n - 2種選擇，以此類推。

我直接用 算法可視化面板 把遞歸樹畫出來，你一眼就可以看懂了。請你把進度條拖到最后讓整棵回溯樹顯示出來，然后把鼠標在每一層節點上橫向移動，觀察遞歸樹節點和樹枝上的值：

圖片

這個可視化面板的網頁地址，你可以自己去試試：

https://labuladong.online/algo/practice-in-action/two-views-of-backtrack/#div_box-view-of-permute

其實這個算法還可以優化，也就是用 swap 的寫法。

我在 回溯算法核心框架 和 回溯算法秒殺排列/組合/子集的九種變體 中都寫了上面這段代碼，很多讀者看了之后就跑來跟我說啊，他看的那個全排列算法是通過swap操作來計算的，不需要used數組的額外空間，比我講解的回溯算法框架效率高，怎么怎么的。

是的，我之所以不用那個swap的解法，是因為前面那兩篇文章的重點在于實踐回溯算法「做選擇」和「撤銷選擇」的思維框架，用used數組的解法更容易讓初學者理解。但從算法效率上說，確實有更高效的代碼實現方法。

下面就滿足大家的好奇心，跟大家講講那個傳說中的swap的解法，到底是何方神圣。

首先，我列出那個使用swap計算全排列的解法代碼，請你先看一下：

class Solution {

    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        backtrack(nums, 0);
        return result;
    }

    // 回溯算法核心框架
    void backtrack(int[] nums, int start) {
        if (start == nums.length) {
            // 找到一個全排列，Java 需要轉化成 List 類型
            List<Integer> list = new ArrayList<>();
            for (int num : nums) {
                list.add(num);
            }
            result.add(list);
            return;
        }

        for (int i = start; i < nums.length; i++) {
            // 做選擇
            swap(nums, start, i);
            // 遞歸調用，傳入 start + 1
            backtrack(result, nums, start + 1);
            // 撤銷選擇
            swap(nums, start, i);
        }
    }

    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

這個解法也可以正確計算全排列，請你思考，這段代碼是以什么視角進行窮舉的？是以球的視角還是盒的視角？

答案是，這個解法是以盒的視角進行窮舉的。即nums數組中的每個索引位置，來選擇不同的元素放入這個索引位置。

你看解法代碼也可以看出來，那個start參數就是當前在選擇元素的索引位置，在start之前的元素已經心有所屬，被其他位置挑走了，所以start位置只能從nums[start..]中選擇元素。

我可以用 算法可視化面板 把遞歸樹畫出來，你一眼就可以看懂了。請你把進度條拖到最后讓整棵回溯樹顯示出來，然后把鼠標在每一層節點上橫向移動，觀察遞歸樹節點和樹枝上的值：

圖片

這個可視化面板的網頁地址，你可以自己去試試：

https://labuladong.online/algo/practice-in-action/two-views-of-backtrack/#div_box-view-of-permute-improved

接下來一個很自然的問題，能不能寫出一個以球的視角理解的全排列問題的解法？

當然可以，以球的視角來寫全排列的解法代碼，就是說nums中的每個元素來選擇自己想去的索引，對吧。有了這個思路，代碼還有何難寫。

我先用 算法可視化面板 把遞歸樹畫出來，請你把進度條拖到最后讓整棵回溯樹顯示出來，然后把鼠標在每一層節點上橫向移動，觀察遞歸樹節點和樹枝上的值，驗證一下是不是元素在選索引：

圖片

這個可視化面板的網頁地址，你可以自己去試試：

https://labuladong.online/algo/practice-in-action/two-views-of-backtrack/#div_ball-view-of-permute

當然我寫的代碼還有一些小優化的空間，比如說這個swapIndex其實就是i，而且我們其實不用等到count == nums.length，當count == nums.length - 1時就可以 return 了，因為最后剩的那個元素的位置不會找不到其他位置了。這些留給你優化吧。

class Solution {
    List<List<Integer>> res; // 結果列表
    boolean[] used; // 標記元素是否已被使用
    int count; // 記錄有多少個元素已經選擇過位置

    public List<List<Integer>> permute(int[] nums) {
        res = new ArrayList<>();
        used = new boolean[nums.length];
        count = 0;

        backtrack(nums);
        return res;
    }

    // 回溯算法框架
    void backtrack(int[] nums) {
        if (count == nums.length) {
            List<Integer> temp = new ArrayList<>();
            for (int num : nums) {
                temp.add(num);
            }
            res.add(temp);
            return;
        }

        // 找兩個未被選擇的位置
        int originalIndex = -1, swapIndex = -1;

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            if (originalIndex == -1) {
                originalIndex = i;
            }
            swapIndex = i;

            // 做選擇，元素 nums[originalIndex] 選擇 swapIndex 位置
            swap(nums, originalIndex, swapIndex);
            used[swapIndex] = true;
            count++;
            // 進入下一層決策樹
            backtrack(nums);
            // 撤銷選擇，剛才怎么做的選擇，就原樣恢復
            count--;
            used[swapIndex] = false;
            swap(nums, originalIndex, swapIndex);
        }
    }

    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

用球盒模型重新理解子集問題

有了前面的鋪墊，我又要進一步為難你了?；厮菟惴霘⑴帕?組合/子集的九種變體 都給出過子集問題的代碼。

就以最基本的元素無重不可復選的子集為例，我直接把代碼 copy 過來：

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

    // 主函數
    public List<List<Integer>> subsets(int[] nums) {
        backtrack(nums, 0);
        return res;
    }

    // 回溯算法核心函數，遍歷子集問題的回溯樹
    void backtrack(int[] nums, int start) {

        // 前序位置，每個節點的值都是一個子集
        res.add(new LinkedList<>(track));

        // 回溯算法標準框架
        for (int i = start; i < nums.length; i++) {
            // 做選擇
            track.addLast(nums[i]);
            // 通過 start 參數控制樹枝的遍歷，避免產生重復的子集
            backtrack(nums, i + 1);
            // 撤銷選擇
            track.removeLast();
        }
    }
}

請問，這個解法是以什么視角進行窮舉的？是以球的視角還是盒的視角？給你三分鐘思考，請回答！

這個解法是以盒的視角窮舉的，即站在nums中的每個索引的視角，來選擇不同的元素放入這個索引位置。

因為剛才講的全排列問題會考慮順序的差異，而子集問題不考慮順序的差異。為了方便理解，我們這里干脆不說「球盒模型」了，說「球桶模型」吧，因為放進盒子的求給人感覺是有順序的，而丟進桶里的東西給人感覺是無所謂順序的。

那么，以桶的視角理解，子集問題相當于把n個球丟到容量為n的桶里，桶可以不裝滿。

這樣，桶的第一個位置可以選擇n個球中的任意一個，比如選擇了球i，然后桶的第二個位置可以選擇球i后面的球中的任意一個（通過固定相對順序保證不會出現重復的子集），以此類推。

你看代碼也能體現出來這種窮舉過程：

// 回溯算法框架核心代碼
void backtrack(int[] nums, int start) {
    for (int i = start; i < nums.length; i++) {
        track.addLast(nums[i]);
        // 通過 start 參數控制樹枝的生長
        backtrack(nums, i + 1);
        track.removeLast();
    }
}

我繼續用 算法可視化面板 來論證我的答案，請你把進度條拖到最后讓整棵回溯樹顯示出來，然后把鼠標在每一層節點上橫向移動，觀察遞歸樹節點和樹枝上的值，你可以很直觀地看明白，是桶的位置在選擇球：

圖片

這個可視化面板的網頁地址，你可以自己去試試：

https://labuladong.online/algo/practice-in-action/two-views-of-backtrack/#div_box-view-of-subsets

既然上面說了，我給的子集問題解法是以桶的視角理解的，那么你能不能寫出一個以球的視角理解的子集問題的解法？給你十分鐘寫代碼。

如果你有這個時間，一定要親自動手嘗試一下，不要著急看我的答案。你能認真看到這里，肯定可以寫出來的。

從球的視角理解，每個球都有兩種選擇，要么在桶中，要么不在桶中。這樣，我們可以寫出下面的代碼：

class Solution {
    List<List<Integer>> res; // 用于存儲所有子集的結果
    List<Integer> track; // 用于存儲當前遞歸路徑的子集

    public List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<>();
        track = new ArrayList<>();
        backtrack(nums, 0);
        return res;
    }

    void backtrack(int[] nums, int i) {
        if (i == nums.length) {
            res.add(new ArrayList<>(track));
            return;
        }

        // 做第一種選擇，元素在子集中
        track.add(nums[i]);
        backtrack(nums, i + 1);
        // 撤銷選擇
        track.remove(track.size() - 1);

        // 做第二種選擇，元素不在子集中
        backtrack(nums, i + 1);
    }
}

我繼續用 算法可視化面板 來論證我的答案，請你把進度條拖到最后讓整棵回溯樹顯示出來，然后把鼠標在節點上移動，觀察遞歸樹節點和樹枝上的值：

圖片

這個可視化面板的網頁地址，你可以自己去試試：

https://labuladong.online/algo/practice-in-action/two-views-of-backtrack/#div_ball-view-of-subsets

這也解釋了，為什么所有子集（冪集）的數量是2^n，因為每個元素都有兩種選擇，要么在子集中，要么不在子集中，所以其遞歸樹就是一棵滿二叉樹，一共有2^n個葉子節點。

結論

照應一下開頭，把幾個結論再重寫一遍，你現在應該更理解了。

1、回溯算法窮舉的本質思維模式是「球盒模型」，一切回溯算法，皆從此出，別無二法。

你現在就去做 100 道回溯算法的題目，看看有沒有意外，有意外你來打我。

2、球盒模型，必然有兩種窮舉視角，分別為「球」的視角窮舉和「盒」的視角窮舉，對應的，就是兩種不同的代碼寫法。

暴力窮舉就是如此樸實無華且枯燥，看起來花里胡哨，實則只有兩種視角。

3、從理論上分析，兩種窮舉視角本質上是一樣的。但是涉及到具體的代碼實現，兩種寫法的復雜度可能有優劣之分。

進一步想想，為啥用「盒」的視角，即讓索引取選元素的視角，可以用swap的方法把used數組給優化掉呢？

因為索引容易處理，如果你按順序從小到大讓每個索引去選元素，那么一個start變量作為分割線就能把已選元素和未選元素分開。

反過來，如果你讓元素去選索引，那就只能依賴額外的數據結構來記錄那些索引已經被選過了，這樣就會增加額外的空間復雜度。

所以說，在開頭的數學分析中，兩種視角在數學上雖然是等價的，但具體到代碼實現上，最優復雜度就可能不一樣。

好的，最后留個懸念：只有寫回溯算法時才會用到「球盒模型」這種思想嗎？

你可以讀一讀 動態規劃算法的兩種視角，思考一下這個問題。