點(diǎn)擊關(guān)注上方“五分鐘學(xué)算法”，

設(shè)為“置頂或星標(biāo)”，第一時(shí)間送達(dá)干貨。

轉(zhuǎn)自面向大象編程

本期例題：LeetCode 46 - Permutations^[1]（Medium）

給定一個(gè)不重復(fù)的數(shù)字集合，返回其所有可能的全排列。例如：

• 輸入：[1, 2, 3]

• 輸出：

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]

在第三講中，我們就講過了回溯法問題的基本思想。回溯法問題用遞歸求解，可以聯(lián)系上樹的遍歷，我們可以將決策路徑畫成一棵樹，回溯的過程就是這棵樹的遍歷過程。

不過在那篇文章中，我們只求解了一道非常簡(jiǎn)單的回溯法問題：子集（subset）問題。在面試中，我們需要有能力更加復(fù)雜的回溯法問題，并應(yīng)對(duì)題目的各種變種。本篇以經(jīng)典的排列（permutation）和組合（combination）問題為例，講講求解回溯法問題的要點(diǎn)：候選集合。

這篇文章將會(huì)包含：

• 回溯法的”選什么“問題與候選集合

• 全排列、排列、組合問題的回溯法解法

• 回溯法問題中，如何維護(hù)候選集合

• 回溯法問題中，如何處理失效元素

回溯法的重點(diǎn)：“選什么”

我們說過，回溯法實(shí)際上就是在一棵決策樹上做遍歷的過程。那么，求解回溯法題目時(shí)，我們首先要思考所有決策路徑的形狀。例如，子集問題的決策樹如下圖所示：

子集問題的決策樹

決策樹形狀主要取決于每個(gè)結(jié)點(diǎn)處可能的分支，換句話說，就是在每次做決策時(shí)，我們 “可以選什么”、 “有什么可選的”。

對(duì)于子集問題而言，這個(gè)“選什么”的問題非常簡(jiǎn)單，每次只有一個(gè)元素可選，要么選、要么不選。不過，對(duì)于更多的回溯法題目，“選什么”的問題并不好回答。這時(shí)候，我們就需要分析問題的候選集合，以及候選集合的變化，以此得到解題的思路。

全排列問題：如何維護(hù)候選集合

讓我們拿經(jīng)典的全排列問題來(lái)講解回溯法問題的候選集合概念。

在全排列問題中，決策樹的分支數(shù)量并不固定。我們一共做? 次決策，第? 次決策會(huì)選擇排列的第? 個(gè)數(shù)。選擇第一個(gè)數(shù)時(shí)，全部的? 個(gè)數(shù)都可供挑選。而由于已選的數(shù)不可以重復(fù)選擇，越往后可供選擇的數(shù)越少。以? 為例，決策樹的形狀如下圖所示：

全排列問題的決策樹

如果從候選集合的角度來(lái)思考，在進(jìn)行第一次選擇時(shí)，全部的 3 個(gè)數(shù)都可以選擇，候選集合的大小為 3。在第二次選擇時(shí)，候選集合的大小就只有 2 了；第三次選擇時(shí)，候選集合只剩一個(gè)元素。可以看到，全排列問題候選集合的變化規(guī)律是：每做一次選擇，候選集合就少一個(gè)元素，直到候選集合選完為止。我們可以在上面的決策樹的每個(gè)結(jié)點(diǎn)旁畫上候選集合的元素，這樣看得更清晰。

全排列問題有候選集合的決策樹

可以看到，已選集合與候選集合是補(bǔ)集的關(guān)系，它們加起來(lái)就是全部的元素。而在回溯法的選擇與撤銷選擇的過程中，已選集合和候選集合是此消彼長(zhǎng)的關(guān)系。

如何根據(jù)這樣的思路寫出代碼呢？當(dāng)然可以用 HashSet 這樣的數(shù)據(jù)結(jié)構(gòu)來(lái)表示候選集合。但如果你這么去寫的話，會(huì)發(fā)現(xiàn)代碼寫起來(lái)比較啰嗦，而且 set 結(jié)構(gòu)的“遍歷-刪除”操作不太好寫。在這里，我不展示使用 set 結(jié)構(gòu)的代碼。大家只要明白一條要點(diǎn)：在一般情況下，候選集合使用數(shù)組表示即可。 候選集合上需要做的操作并不是很多，使用數(shù)組簡(jiǎn)單又高效。

在子集問題中，我們定義了變量 k，表示當(dāng)前要對(duì)第 k 個(gè)元素做決策。實(shí)際上，變量 k 就是候選集合的邊界，指針 k 之后的元素都是候選元素，而 k 之前都是無(wú)效元素，不可以再選了。

用數(shù)組表示候選集合

而每次決策完之后將 k 加一，就是將第 k 個(gè)元素移出了候選集合。

將第 k 個(gè)元素移出候選集合

在全排列問題中，我們要處理的情況更難一些。每次做決策時(shí)，候選集合中的所有元素都可以選擇，也就是有可能刪除候選集合中間的元素，這樣數(shù)組中會(huì)出現(xiàn)“空洞”。這種情況該怎么處理呢？我們可以使用一個(gè)巧妙的方法，先將要?jiǎng)h除的元素與第 k 個(gè)元素交換，再將 k 加一，過程如下方動(dòng)圖所示：

從候選集合中部刪除元素（動(dòng)圖）

不知道你有沒有注意到，上圖中候選集合之外的元素畫成了藍(lán)色，這些實(shí)際上就是已選集合。前面分析過，已選集合與候選集合是互補(bǔ)的。將藍(lán)色部分看成已選集合的話，我們從候選集合中刪除的元素，正好加入了已選集合中。也就是說，我們可以只用一個(gè)數(shù)組同時(shí)表示已選集合和候選集合！

理解了圖中的關(guān)系之后，題解代碼就呼之欲出了。我們只需使用一個(gè) current 數(shù)組，左半邊表示已選元素，右半邊表示候選元素。指針 k 不僅是候選元素的開始位置，還是已選元素的結(jié)束位置。我們可以得到一份非常簡(jiǎn)潔的題解代碼：

public List<List<Integer>> permute(List<Integer> nums) {List<Integer> current = new ArrayList<>(nums);List<List<Integer>> res = new ArrayList<>();backtrack(current, 0, res);return res; }// current[0..k) 是已選集合， current[k..N) 是候選集合 void backtrack(List<Integer> current, int k, List<List<Integer>> res) {if (k == current.size()) {res.add(new ArrayList<>(current));return;}// 從候選集合中選擇for (int i = k; i < current.size(); i++) {// 選擇數(shù)字 current[i]Collections.swap(current, k, i);// 將 k 加一backtrack(current, k+1, res);// 撤銷選擇Collections.swap(current, k, i);} }

注意寫在遞歸函數(shù)上方的注釋。在寫回溯法問題的代碼時(shí)，你需要時(shí)刻清楚什么是已選集合，什么是候選集合。注釋中的條件叫做“不變式”。一方面，我們?cè)诤瘮?shù)中可以參考變量 k 的含義，另一方面，我們?cè)谧鲞f歸調(diào)用的時(shí)候，要保證這個(gè)條件始終成立。特別注意代碼中遞歸調(diào)用傳入的參數(shù)是 k+1 ，即刪除一個(gè)候選元素，而不是傳入 i+1。

n 中取 k 的排列

全排列問題是? 中取? 的排列，可以記為?。在面試中，我們很可能會(huì)遇到各種各樣的變種題，那么? 中取? 的排列?、組合? 我們也要掌握。

問題非常簡(jiǎn)單，我們只需要在全排列的基礎(chǔ)上，做完第? 個(gè)決策后就將結(jié)果返回。也就是說，只遍歷決策樹的前? 層。例如? 時(shí)，決策樹的第 2 層，已選集合中有兩個(gè)元素，將這里的結(jié)果返回即可。

n 中取 k 的排列的決策樹

題解代碼如下所示，只需要修改遞歸結(jié)束的條件即可。

public List<List<Integer>> permute(List<Integer> nums, int k) {List<Integer> current = new ArrayList<>(nums);List<List<Integer>> res = new ArrayList<>();backtrack(k, current, 0, res);return res; }// current[0..m) 是已選集合， current[m..N) 是候選集合 void backtrack(int k, List<Integer> current, int m, List<List<Integer>> res) {// 當(dāng)已選集合達(dá)到 k 個(gè)元素時(shí)，收集結(jié)果并停止選擇if (m == k) {res.add(new ArrayList<>(current.subList(0, k)));return;}// 從候選集合中選擇for (int i = m; i < current.size(); i++) {// 選擇數(shù)字 current[i]Collections.swap(current, m, i);backtrack(k, current, m+1, res);// 撤銷選擇Collections.swap(current, m, i);} }

注意這里? 是題目的輸入，所以原先我們代碼里的變量 k 重命名成了 m。此外，就是遞歸函數(shù)開頭的 if 語(yǔ)句條件發(fā)生了變化，當(dāng)已選集合達(dá)到? 個(gè)元素時(shí)，就收集結(jié)果停止遞歸。

組合問題：失效元素

由于排列組合的密切聯(lián)系，組合問題? ，即? 中取? 的組合，可以在? 問題的解法上稍加修改而來(lái)。

我們先思考一下組合和排列的關(guān)系。元素相同，但順序不同的兩個(gè)結(jié)果視為不同的排列，例如? 和?。但順序不同的結(jié)果會(huì)視為同一組合。那么，我們只需要考慮? 中所有升序的結(jié)果，就自然完成了組合的去重，得到?。

那么，如何讓回溯只生成升序的排列呢？這需要稍微動(dòng)點(diǎn)腦筋，但也不是很難，只需要做到：每當(dāng)選擇了一個(gè)數(shù)? 時(shí)，將候選集合中的所有小于? 的元素刪除，不再作為候選元素。

再仔細(xì)想想的話，在排列問題為了維護(hù)候選集合而進(jìn)行的交換操作，這里也不需要了。例如下面的例子，選擇元素 6 之后，為了保持結(jié)果升序，前面的元素 4、5 也不能要了。不過，我們并不需要關(guān)注失效元素，我們只需要關(guān)注候選集合的變化情況。我們發(fā)現(xiàn)，剩下的候選集合仍然是數(shù)組中連續(xù)的一段，不會(huì)出現(xiàn)排列問題中的“空洞”情況。我們只用一個(gè)指針就能表示新的候選集合。

從候選集合中刪除多個(gè)元素

下圖是? 的決策樹，可以看到，候選集合都是連續(xù)的。已選集合不連續(xù)沒有關(guān)系，我們可以另開一個(gè)數(shù)組保存已選元素。

組合問題的決策樹

按照這個(gè)思路，我們可以寫出? 的代碼。

public List<List<Integer>> combine(List<Integer> nums, int k) {Deque<Integer> current = new ArrayDeque<>();List<List<Integer>> res = new ArrayList<>();backtrack(k, nums, 0, current, res);return res; }// current 是已選集合， nums[m..N) 是候選集合 void backtrack(int k, List<Integer> nums, int m, Deque<Integer> current, List<List<Integer>> res) {// 當(dāng)已選集合達(dá)到 k 個(gè)元素時(shí)，收集結(jié)果并停止選擇if (current.size() == k) {res.add(new ArrayList<>(current));return;}// 從候選集合中選擇for (int i = m; i < nums.size(); i++) {// 選擇數(shù)字 nums[i]current.addLast(nums.get(i));// 元素 nums[m..i) 均失效backtrack(k, nums, i+1, current, res);// 撤銷選擇current.removeLast();} }

由于已選集合與候選集合并非互補(bǔ)，這里用單獨(dú)的數(shù)組存儲(chǔ)已選元素，這一點(diǎn)上與子集問題類似。

組合問題與子集問題的關(guān)系

也許是排列 & 組合的 CP 感太重，所以我們?cè)谒伎冀M合問題的解法的時(shí)候會(huì)自然地從排列問題上遷移。其實(shí)，組合問題和子集問題有很密切的聯(lián)系。

由子集問題求解組合問題

組合問題可以看成是子集問題的特殊情況。從? 中取? 個(gè)數(shù)的組合，實(shí)際上就是求? 個(gè)元素的所有大小為? 的子集。也就是說，組合問題的結(jié)果是子集問題的一部分。我們可以在子集問題的決策樹的基礎(chǔ)上，當(dāng)已選集合大小為? 的時(shí)候就不再遞歸，就可以得到組合問題的決策樹。

在子集問題決策樹基礎(chǔ)上得到的組合問題決策樹

具體的代碼這里就不展示了，請(qǐng)讀者自行在子集問題的題解代碼的基礎(chǔ)上修改得到? 的代碼。

由組合問題求解子集問題

對(duì)于子集問題，大小為? 的集合共有? 個(gè)可能的子集。對(duì)于組合問題?，得到的結(jié)果個(gè)數(shù)是組合數(shù)?，或者記為?。根據(jù)二項(xiàng)式定理：

要得到全部的? 個(gè)子集，我們可以計(jì)算所有? 中取? 的組合，再把這些組合加起來(lái)。根據(jù)這個(gè)思路，我們可以在組合問題的題解代碼上稍加修改得到子集問題的解：

public List<List<Integer>> subsets(List<Integer> nums) {Deque<Integer> current = new ArrayDeque<>();List<List<Integer>> res = new ArrayList<>();backtrack(nums, 0, current, res);return res; }// current 是已選集合， nums[m..N) 是候選集合 void backtrack(List<Integer> nums, int m, Deque<Integer> current, List<List<Integer>> res) {// 收集決策樹上每一個(gè)結(jié)點(diǎn)的結(jié)果res.add(new ArrayList<>(current));if (m == nums.size()) {// 當(dāng)候選集合為空時(shí)，停止遞歸return;}// 從候選集合中選擇for (int i = m; i < nums.size(); i++) {// 選擇數(shù)字 nums[i]current.addLast(nums.get(i));// 元素 nums[m..i) 均失效backtrack(nums, i+1, current, res);// 撤銷選擇current.removeLast();} }

可以看到，每次做決策都會(huì)增加一個(gè)已選元素。當(dāng)遞歸到第? 層時(shí)，計(jì)算的就是大小為? 的子集。不過，這樣寫出的子集問題解法沒有原解法易懂，我還是更推薦原解法。

總結(jié)

排列組合問題是回溯法中非常實(shí)際也非常典型的例題，可以通過做這些題目來(lái)體會(huì)回溯法的基本技巧。不過它們?cè)?LeetCode 中沒有完全對(duì)應(yīng)的例題。文章開頭的例題是全排列問題。對(duì)于組合問題，LeetCode 只有一個(gè)簡(jiǎn)化版 77. Combinations^[2]，其中數(shù)字固定為 1 到 n 的整數(shù)。

排列組合問題展示了在求解回溯法問題時(shí)，候選集合的概念對(duì)理清思路的重要性。實(shí)際上，回溯法中的“選擇”與“撤銷選擇”，實(shí)際上就是從候選集合中刪除元素與添加回元素的操作。而我們?cè)趯懘a的時(shí)候要注意在遞歸函數(shù)上方寫注釋，明確數(shù)組的哪一部分是候選集合。

排列組合問題還存在著一些變種，例如當(dāng)輸入存在重復(fù)元素的時(shí)候，如何避免結(jié)果重復(fù)，就需要使用決策樹的剪枝方法。下一篇文章將會(huì)講解回溯法問題中如何正確地剪枝。

參考資料

[1]

LeetCode 46 - Permutations: https://leetcode.com/problems/permutations/

[2]

77. Combinations: https://leetcode.com/problems/combinations/

---

推薦閱讀

?? ?C++是如何從代碼到游戲的？?? ?告訴你一個(gè)學(xué)習(xí)編程的訣竅（建議收藏）?? ?自學(xué)編程的八大誤區(qū)！克服它！?? ?新手如何有效的刷算法題（LeetCode）?? ?10款VS Code插件神器，第7款超級(jí)實(shí)用！?? ?在拼多多上班，是一種什么樣的體驗(yàn)？我tm心態(tài)崩了呀！?? ?寫給小白，從零開始擁有一個(gè)酷炫上線的網(wǎng)站！

---

歡迎關(guān)注我的公眾號(hào)“五分鐘學(xué)算法”，如果喜歡，麻煩點(diǎn)一下“在看”~

總結(jié)

以上是生活随笔為你收集整理的LeetCode 例题精讲 | 08 排列组合问题：回溯法的候选集合的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。