讀完本文，你可以去力扣拿下如下題目：
-----------
今天就來聊三道考察頻率高恬砂，而且容易讓人搞混的算法問題咧纠，分別是求子集（subset），求排列（permutation）泻骤，求組合（combination）惧盹。
這幾個(gè)問題都可以用回溯算法模板解決，同時(shí)子集問題還可以用數(shù)學(xué)歸納思想解決瞪讼。讀者可以記住這幾個(gè)問題的回溯套路钧椰，就不怕搞不清了。
一符欠、子集
問題很簡單嫡霞，輸入一個(gè)不包含重復(fù)數(shù)字的數(shù)組，要求算法輸出這些數(shù)字的所有子集希柿。
vector<vector<int>> subsets(vector<int>& nums);
比如輸入 nums = [1,2,3]诊沪，你的算法應(yīng)輸出 8 個(gè)子集养筒，包含空集和本身，順序可以不同：
[ [],[1],[2],[3],[1,3],[2,3],[1,2],[1,2,3] ]
第一個(gè)解法是利用數(shù)學(xué)歸納的思想：假設(shè)我現(xiàn)在知道了規(guī)模更小的子問題的結(jié)果端姚，如何推導(dǎo)出當(dāng)前問題的結(jié)果呢晕粪？
具體來說就是，現(xiàn)在讓你求 [1,2,3] 的子集渐裸，如果你知道了 [1,2] 的子集巫湘，是否可以推導(dǎo)出 [1,2,3] 的子集呢？先把 [1,2] 的子集寫出來瞅瞅：
[ [],[1],[2],[1,2] ]
你會發(fā)現(xiàn)這樣一個(gè)規(guī)律：
subset([1,2,3]) - subset([1,2])
= [3],[1,3],[2,3],[1,2,3]
而這個(gè)結(jié)果昏鹃，就是把 sebset([1,2]) 的結(jié)果中每個(gè)集合再添加上 3尚氛。
換句話說，如果 A = subset([1,2]) 洞渤，那么：
subset([1,2,3])
= A + [A[i].add(3) for i = 1..len(A)]
這就是一個(gè)典型的遞歸結(jié)構(gòu)嘛阅嘶，[1,2,3] 的子集可以由 [1,2] 追加得出，[1,2] 的子集可以由 [1] 追加得出载迄，base case 顯然就是當(dāng)輸入集合為空集時(shí)讯柔，輸出子集也就是一個(gè)空集。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)护昧，手把手刷 200 道力扣題目磷杏，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新捏卓。建議收藏极祸，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了怠晴。
翻譯成代碼就很容易理解了：
vector<vector<int>> subsets(vector<int>& nums) {
// base case遥金，返回一個(gè)空集
if (nums.empty()) return {{}};
// 把最后一個(gè)元素拿出來
int n = nums.back();
nums.pop_back();
// 先遞歸算出前面元素的所有子集
vector<vector<int>> res = subsets(nums);
int size = res.size();
for (int i = 0; i < size; i++) {
// 然后在之前的結(jié)果之上追加
res.push_back(res[i]);
res.back().push_back(n);
}
return res;
}
這個(gè)問題的時(shí)間復(fù)雜度計(jì)算比較容易坑人。我們之前說的計(jì)算遞歸算法時(shí)間復(fù)雜度的方法蒜田，是找到遞歸深度稿械，然后乘以每次遞歸中迭代的次數(shù)。對于這個(gè)問題冲粤，遞歸深度顯然是 N美莫，但我們發(fā)現(xiàn)每次遞歸 for 循環(huán)的迭代次數(shù)取決于 res 的長度，并不是固定的梯捕。
根據(jù)剛才的思路厢呵，res 的長度應(yīng)該是每次遞歸都翻倍，所以說總的迭代次數(shù)應(yīng)該是 2^N傀顾〗竺或者不用這么麻煩，你想想一個(gè)大小為 N 的集合的子集總共有幾個(gè)？2^N 個(gè)對吧寒砖，所以說至少要對 res 添加 2^N 次元素赐劣。
那么算法的時(shí)間復(fù)雜度就是 O(2^N) 嗎？還是不對哩都，2^N 個(gè)子集是 push_back 添加進(jìn) res 的魁兼，所以要考慮 push_back 這個(gè)操作的效率：
for (int i = 0; i < size; i++) {
res.push_back(res[i]); // O(N)
res.back().push_back(n); // O(1)
}
因?yàn)?res[i] 也是一個(gè)數(shù)組呀，push_back 是把 res[i] copy 一份然后添加到數(shù)組的最后漠嵌，所以一次操作的時(shí)間是 O(N)咐汞。
綜上，總的時(shí)間復(fù)雜度就是 O(N*2^N)献雅，還是比較耗時(shí)的碉考。
空間復(fù)雜度的話塌计，如果不計(jì)算儲存返回結(jié)果所用的空間的挺身，只需要 O(N) 的遞歸堆棧空間锌仅。如果計(jì)算 res 所需的空間章钾，應(yīng)該是 O(N*2^N)。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)热芹，手把手刷 200 道力扣題目贱傀，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新伊脓。建議收藏府寒，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了报腔。
第二種通用方法就是回溯算法株搔。舊文「回溯算法詳解」寫過回溯算法的模板：
result = []
def backtrack(路徑, 選擇列表):
if 滿足結(jié)束條件:
result.add(路徑)
return
for 選擇 in 選擇列表:
做選擇
backtrack(路徑, 選擇列表)
撤銷選擇
只要改造回溯算法的模板就行了：
vector<vector<int>> res;
vector<vector<int>> subsets(vector<int>& nums) {
// 記錄走過的路徑
vector<int> track;
backtrack(nums, 0, track);
return res;
}
void backtrack(vector<int>& nums, int start, vector<int>& track) {
res.push_back(track);
for (int i = start; i < nums.size(); i++) {
// 做選擇
track.push_back(nums[i]);
// 回溯
backtrack(nums, i + 1, track);
// 撤銷選擇
track.pop_back();
}
}
可以看見，對 res 更新的位置處在前序遍歷纯蛾，也就是說纤房，res 就是樹上的所有節(jié)點(diǎn)：
二、組合
輸入兩個(gè)數(shù)字 n, k翻诉，算法輸出 [1..n] 中 k 個(gè)數(shù)字的所有組合炮姨。
vector<vector<int>> combine(int n, int k);
比如輸入 n = 4, k = 2，輸出如下結(jié)果碰煌，順序無所謂舒岸，但是不能包含重復(fù)（按照組合的定義，[1,2] 和 [2,1] 也算重復(fù)）：
[
[1,2],
[1,3],
[1,4],
[2,3],
[2,4],
[3,4]
]
這也是典型的回溯算法芦圾，k 限制了樹的高度吁津，n 限制了樹的寬度，繼續(xù)套我們以前講過的回溯算法模板框架就行了：
vector<vector<int>>res;
vector<vector<int>> combine(int n, int k) {
if (k <= 0 || n <= 0) return res;
vector<int> track;
backtrack(n, k, 1, track);
return res;
}
void backtrack(int n, int k, int start, vector<int>& track) {
// 到達(dá)樹的底部
if (k == track.size()) {
res.push_back(track);
return;
}
// 注意 i 從 start 開始遞增
for (int i = start; i <= n; i++) {
// 做選擇
track.push_back(i);
backtrack(n, k, i + 1, track);
// 撤銷選擇
track.pop_back();
}
}
backtrack 函數(shù)和計(jì)算子集的差不多，區(qū)別在于碍脏，更新 res 的時(shí)機(jī)是樹到達(dá)底端時(shí)梭依。
三、排列
輸入一個(gè)不包含重復(fù)數(shù)字的數(shù)組 nums典尾，返回這些數(shù)字的全部排列役拴。
vector<vector<int>> permute(vector<int>& nums);
比如說輸入數(shù)組 [1,2,3]，輸出結(jié)果應(yīng)該如下钾埂，順序無所謂河闰，不能有重復(fù)：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
「回溯算法詳解」中就是拿這個(gè)問題來解釋回溯模板的。這里又列出這個(gè)問題褥紫，是將「排列」和「組合」這兩個(gè)回溯算法的代碼拿出來對比姜性。
首先畫出回溯樹來看一看：
我們當(dāng)時(shí)使用 Java 代碼寫的解法：
List<List<Integer>> res = new LinkedList<>();
/* 主函數(shù)，輸入一組不重復(fù)的數(shù)字髓考，返回它們的全排列 */
List<List<Integer>> permute(int[] nums) {
// 記錄「路徑」
LinkedList<Integer> track = new LinkedList<>();
backtrack(nums, track);
return res;
}
void backtrack(int[] nums, LinkedList<Integer> track) {
// 觸發(fā)結(jié)束條件
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// 排除不合法的選擇
if (track.contains(nums[i]))
continue;
// 做選擇
track.add(nums[i]);
// 進(jìn)入下一層決策樹
backtrack(nums, track);
// 取消選擇
track.removeLast();
}
}
回溯模板依然沒有變部念，但是根據(jù)排列問題和組合問題畫出的樹來看，排列問題的樹比較對稱氨菇，而組合問題的樹越靠右節(jié)點(diǎn)越少儡炼。
在代碼中的體現(xiàn)就是，排列問題每次通過 contains 方法來排除在 track 中已經(jīng)選擇過的數(shù)字查蓉；而組合問題通過傳入一個(gè) start 參數(shù)乌询，來排除 start 索引之前的數(shù)字。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)豌研，手把手刷 200 道力扣題目妹田，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新鹃共。建議收藏鬼佣，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了及汉。
以上沮趣，就是排列組合和子集三個(gè)問題的解法，總結(jié)一下：
子集問題可以利用數(shù)學(xué)歸納思想坷随，假設(shè)已知一個(gè)規(guī)模較小的問題的結(jié)果房铭，思考如何推導(dǎo)出原問題的結(jié)果。也可以用回溯算法温眉，要用 start 參數(shù)排除已選擇的數(shù)字缸匪。
組合問題利用的是回溯思想，結(jié)果可以表示成樹結(jié)構(gòu)类溢，我們只要套用回溯算法模板即可凌蔬，關(guān)鍵點(diǎn)在于要用一個(gè) start 排除已經(jīng)選擇過的數(shù)字露懒。
排列問題是回溯思想，也可以表示成樹結(jié)構(gòu)套用算法模板砂心，關(guān)鍵點(diǎn)在于使用 contains 方法排除已經(jīng)選擇的數(shù)字懈词，前文有詳細(xì)分析，這里主要是和組合問題作對比辩诞。
記住這幾種樹的形狀坎弯，就足以應(yīng)對大部分回溯算法問題了，無非就是 start 或者 contains 剪枝译暂，也沒啥別的技巧了抠忘。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目外永，建議收藏播掷！對應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star州既，歡迎標(biāo)星罗侯！
