球盒模型：一切回溯窮舉，皆從此法出
在這篇文章，我不僅會具體介紹之前沒有講到的回溯算法寫法，還會告訴你為什么可以那樣寫，兩種寫法的本質區別是什么。
先說結論：
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變量作為分割線就能把已選元素和未選元素分開。
反過來，如果你讓元素去選索引，那就只能依賴額外的數據結構來記錄那些索引已經被選過了，這樣就會增加額外的空間復雜度。
所以說，在開頭的數學分析中，兩種視角在數學上雖然是等價的，但具體到代碼實現上，最優復雜度就可能不一樣。
好的，最后留個懸念：只有寫回溯算法時才會用到「球盒模型」這種思想嗎？
你可以讀一讀 動態規劃算法的兩種視角，思考一下這個問題。
