球盒模型：一切回溯窮舉，皆從此法出

作者：labuladong 2024-03-28 08:24:01

開發(fā) 前端

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

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

先說結(jié)論：

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

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

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

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

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

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

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

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

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

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

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

圖片

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

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

圖片

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

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

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

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

圖片

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

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

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

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

圖片

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

圖片

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

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

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

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

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

class Solution {

    List<List<Integer>> res = new LinkedList<>();
    // 記錄回溯算法的遞歸路徑
    LinkedList<Integer> track = new LinkedList<>();
    // track 中的元素會被標(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;
        }
    }
}

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

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

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

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

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

圖片

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

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

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

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

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

下面就滿足大家的好奇心，跟大家講講那個傳說中的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 需要轉(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;
    }
}

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

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

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

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

圖片

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

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

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

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

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

圖片

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

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

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

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

    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++;
            // 進(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;
    }
}

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

有了前面的鋪墊，我又要進(jìn)一步為難你了。回溯算法秒殺排列/組合/子集的九種變體都給出過子集問題的代碼。

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

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ù)，遍歷子集問題的回溯樹
    void backtrack(int[] nums, int start) {

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

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

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

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

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

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

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

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

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

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

圖片

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

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

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

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

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

class Solution {
    List<List<Integer>> res; // 用于存儲所有子集的結(jié)果
    List<Integer> track; // 用于存儲當(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ù)用算法可視化面板來論證我的答案，請你把進(jìn)度條拖到最后讓整棵回溯樹顯示出來，然后把鼠標(biāo)在節(jié)點(diǎn)上移動，觀察遞歸樹節(jié)點(diǎn)和樹枝上的值：

圖片