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

先說(shuō)結(jié)論：

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

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

3、從理論上分析，兩種窮舉視角本質(zhì)上是一樣的。但是涉及到具體的代碼實(shí)現(xiàn)，兩種寫法的復(fù)雜度可能有優(yōu)劣之分。你需要選擇效率更高的寫法。

球盒模型這個(gè)詞是我隨口編的，因?yàn)橄旅嫖視?huì)用「球」和「盒」兩種視角來(lái)解釋，你理解就好。

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

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

你懂了這個(gè)，就可以隨心所欲運(yùn)用暴力窮舉算法，下面的內(nèi)容，請(qǐng)你仔細(xì)看，認(rèn)真想。

首先，我們回顧一下以前學(xué)過(guò)的排列組合知識(shí)：

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

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

3、排列、組合總數(shù)的計(jì)算公式：

圖片

好，現(xiàn)在我問(wèn)一個(gè)問(wèn)題，這個(gè)排列公式P(n, k)是如何推導(dǎo)出來(lái)的？為了搞清楚這個(gè)問(wèn)題，我需要講一點(diǎn)組合數(shù)學(xué)的知識(shí)。

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

圖片

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

現(xiàn)在你來(lái)，往盒子里放球，你怎么放？其實(shí)有兩種視角。

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

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

圖片

另外，你也可以站在球的視角，因?yàn)椴⒉皇敲總€(gè)球都會(huì)被裝進(jìn)盒子，所以球的視角分兩種情況：

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

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

結(jié)合上述兩種情況，可以得到：

圖片

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

圖片

至于如何解遞歸式，涉及數(shù)學(xué)的內(nèi)容比較多，這里就不做深入探討了，有興趣的讀者可以自行學(xué)習(xí)組合數(shù)學(xué)相關(guān)知識(shí)。

用球盒模型重新理解全排列問(wèn)題

好，上面從數(shù)學(xué)的角度介紹了全排列窮舉的兩種視角，現(xiàn)在回歸到代碼上，我要考你了哦。

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

就以最基本的元素?zé)o重不可復(fù)選的全排列為例，我直接把代碼 copy 過(guò)來(lái)：

class Solution {

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

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

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

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

請(qǐng)問(wèn)，這個(gè)解法是以什么視角進(jìn)行窮舉的？是以球的視角還是盒的視角？給你三分鐘思考，請(qǐng)回答！

這個(gè)代碼是以盒的視角進(jìn)行窮舉的，即站在每個(gè)位置的角度來(lái)選擇球，站在nums中的每個(gè)索引，來(lái)選擇不同的元素放入這個(gè)索引位置。

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

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

我直接用 算法可視化面板 把遞歸樹畫出來(lái)，你一眼就可以看懂了。請(qǐng)你把進(jìn)度條拖到最后讓整棵回溯樹顯示出來(lái)，然后把鼠標(biāo)在每一層節(jié)點(diǎn)上橫向移動(dòng)，觀察遞歸樹節(jié)點(diǎn)和樹枝上的值：

圖片

這個(gè)可視化面板的網(wǎng)頁(yè)地址，你可以自己去試試：

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

其實(shí)這個(gè)算法還可以優(yōu)化，也就是用 swap 的寫法。

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

是的，我之所以不用那個(gè)swap的解法，是因?yàn)榍懊婺莾善恼碌闹攸c(diǎn)在于實(shí)踐回溯算法「做選擇」和「撤銷選擇」的思維框架，用used數(shù)組的解法更容易讓初學(xué)者理解。但從算法效率上說(shuō)，確實(shí)有更高效的代碼實(shí)現(xiàn)方法。

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

首先，我列出那個(gè)使用swap計(jì)算全排列的解法代碼，請(qǐng)你先看一下：

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) {
            // 找到一個(gè)全排列，Java 需要轉(zhuǎn)化成 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);
            // 遞歸調(diào)用，傳入 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;
    }
}

這個(gè)解法也可以正確計(jì)算全排列，請(qǐng)你思考，這段代碼是以什么視角進(jìn)行窮舉的？是以球的視角還是盒的視角？

答案是，這個(gè)解法是以盒的視角進(jìn)行窮舉的。即nums數(shù)組中的每個(gè)索引位置，來(lái)選擇不同的元素放入這個(gè)索引位置。

你看解法代碼也可以看出來(lái)，那個(gè)start參數(shù)就是當(dāng)前在選擇元素的索引位置，在start之前的元素已經(jīng)心有所屬，被其他位置挑走了，所以start位置只能從nums[start..]中選擇元素。

我可以用 算法可視化面板 把遞歸樹畫出來(lái)，你一眼就可以看懂了。請(qǐng)你把進(jìn)度條拖到最后讓整棵回溯樹顯示出來(lái)，然后把鼠標(biāo)在每一層節(jié)點(diǎn)上橫向移動(dòng)，觀察遞歸樹節(jié)點(diǎn)和樹枝上的值：

圖片

這個(gè)可視化面板的網(wǎng)頁(yè)地址，你可以自己去試試：

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

接下來(lái)一個(gè)很自然的問(wèn)題，能不能寫出一個(gè)以球的視角理解的全排列問(wèn)題的解法？

當(dāng)然可以，以球的視角來(lái)寫全排列的解法代碼，就是說(shuō)nums中的每個(gè)元素來(lái)選擇自己想去的索引，對(duì)吧。有了這個(gè)思路，代碼還有何難寫。

我先用 算法可視化面板 把遞歸樹畫出來(lái)，請(qǐng)你把進(jìn)度條拖到最后讓整棵回溯樹顯示出來(lái)，然后把鼠標(biāo)在每一層節(jié)點(diǎn)上橫向移動(dòng)，觀察遞歸樹節(jié)點(diǎn)和樹枝上的值，驗(yàn)證一下是不是元素在選索引：

圖片

這個(gè)可視化面板的網(wǎng)頁(yè)地址，你可以自己去試試：

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

當(dāng)然我寫的代碼還有一些小優(yōu)化的空間，比如說(shuō)這個(gè)swapIndex其實(shí)就是i，而且我們其實(shí)不用等到count == nums.length，當(dāng)count == nums.length - 1時(shí)就可以 return 了，因?yàn)樽詈笫５哪莻€(gè)元素的位置不會(huì)找不到其他位置了。這些留給你優(yōu)化吧。

class Solution {
    List<List<Integer>> res; // 結(jié)果列表
    boolean[] used; // 標(biāo)記元素是否已被使用
    int count; // 記錄有多少個(gè)元素已經(jīng)選擇過(guò)位置

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

        // 找兩個(gè)未被選擇的位置
        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++;
            // 進(jìn)入下一層決策樹
            backtrack(nums);
            // 撤銷選擇，剛才怎么做的選擇，就原樣恢復(fù)
            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;
    }
}

用球盒模型重新理解子集問(wèn)題

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

就以最基本的元素?zé)o重不可復(fù)選的子集為例，我直接把代碼 copy 過(guò)來(lái)：

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

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

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

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

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

請(qǐng)問(wèn)，這個(gè)解法是以什么視角進(jìn)行窮舉的？是以球的視角還是盒的視角？給你三分鐘思考，請(qǐng)回答！

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

因?yàn)閯偛胖v的全排列問(wèn)題會(huì)考慮順序的差異，而子集問(wèn)題不考慮順序的差異。為了方便理解，我們這里干脆不說(shuō)「球盒模型」了，說(shuō)「球桶模型」吧，因?yàn)榉胚M(jìn)盒子的求給人感覺(jué)是有順序的，而丟進(jìn)桶里的東西給人感覺(jué)是無(wú)所謂順序的。

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

這樣，桶的第一個(gè)位置可以選擇n個(gè)球中的任意一個(gè)，比如選擇了球i，然后桶的第二個(gè)位置可以選擇球i后面的球中的任意一個(gè)（通過(guò)固定相對(duì)順序保證不會(huì)出現(xiàn)重復(fù)的子集），以此類推。

你看代碼也能體現(xiàn)出來(lái)這種窮舉過(guò)程：

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

我繼續(xù)用 算法可視化面板 來(lái)論證我的答案，請(qǐng)你把進(jìn)度條拖到最后讓整棵回溯樹顯示出來(lái)，然后把鼠標(biāo)在每一層節(jié)點(diǎn)上橫向移動(dòng)，觀察遞歸樹節(jié)點(diǎn)和樹枝上的值，你可以很直觀地看明白，是桶的位置在選擇球：

圖片

這個(gè)可視化面板的網(wǎng)頁(yè)地址，你可以自己去試試：

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

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

如果你有這個(gè)時(shí)間，一定要親自動(dòng)手嘗試一下，不要著急看我的答案。你能認(rèn)真看到這里，肯定可以寫出來(lái)的。

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

class Solution {
    List<List<Integer>> res; // 用于存儲(chǔ)所有子集的結(jié)果
    List<Integer> track; // 用于存儲(chǔ)當(dāng)前遞歸路徑的子集

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

我繼續(xù)用 算法可視化面板 來(lái)論證我的答案，請(qǐng)你把進(jìn)度條拖到最后讓整棵回溯樹顯示出來(lái)，然后把鼠標(biāo)在節(jié)點(diǎn)上移動(dòng)，觀察遞歸樹節(jié)點(diǎn)和樹枝上的值：

圖片

這個(gè)可視化面板的網(wǎng)頁(yè)地址，你可以自己去試試：

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

這也解釋了，為什么所有子集（冪集）的數(shù)量是2^n，因?yàn)槊總€(gè)元素都有兩種選擇，要么在子集中，要么不在子集中，所以其遞歸樹就是一棵滿二叉樹，一共有2^n個(gè)葉子節(jié)點(diǎn)。

結(jié)論

照應(yīng)一下開頭，把幾個(gè)結(jié)論再重寫一遍，你現(xiàn)在應(yīng)該更理解了。

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

你現(xiàn)在就去做 100 道回溯算法的題目，看看有沒(méi)有意外，有意外你來(lái)打我。

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

暴力窮舉就是如此樸實(shí)無(wú)華且枯燥，看起來(lái)花里胡哨，實(shí)則只有兩種視角。

3、從理論上分析，兩種窮舉視角本質(zhì)上是一樣的。但是涉及到具體的代碼實(shí)現(xiàn)，兩種寫法的復(fù)雜度可能有優(yōu)劣之分。

進(jìn)一步想想，為啥用「盒」的視角，即讓索引取選元素的視角，可以用swap的方法把used數(shù)組給優(yōu)化掉呢？

因?yàn)樗饕菀滋幚?，如果你按順序從小到大讓每個(gè)索引去選元素，那么一個(gè)start變量作為分割線就能把已選元素和未選元素分開。

反過(guò)來(lái)，如果你讓元素去選索引，那就只能依賴額外的數(shù)據(jù)結(jié)構(gòu)來(lái)記錄那些索引已經(jīng)被選過(guò)了，這樣就會(huì)增加額外的空間復(fù)雜度。

所以說(shuō)，在開頭的數(shù)學(xué)分析中，兩種視角在數(shù)學(xué)上雖然是等價(jià)的，但具體到代碼實(shí)現(xiàn)上，最優(yōu)復(fù)雜度就可能不一樣。

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

你可以讀一讀 動(dòng)態(tài)規(guī)劃算法的兩種視角，思考一下這個(gè)問(wèn)題。