來源公眾號：labuladong
作者：labuladong
今天就來聊三道考察頻率高红选，而且容易讓人搞混的算法問題隙疚，分別是求子集（subset）弦讽，求排列（permutation）粟矿，求組合（combination）凰棉。這幾個問題都可以用回溯算法解決。
一陌粹、子集
問題很簡單撒犀，輸入一個不包含重復數(shù)字的數(shù)組，要求算法輸出這些數(shù)字的所有子集掏秩。
vector<vector<int>> subsets(vector<int>& nums);
比如輸入 nums = [1,2,3]绘证，你的算法應輸出 8 個子集，包含空集和本身哗讥，順序可以不同：
[ [],[1],[2],[3],[1,3],[2,3],[1,2],[1,2,3] ]
第一個解法是利用數(shù)學歸納的思想：假設我現(xiàn)在知道了規(guī)模更小的子問題的結(jié)果嚷那，如何推導出當前問題的結(jié)果呢？
具體來說就是杆煞，現(xiàn)在讓你求 [1,2,3] 的子集魏宽，如果你知道了 [1,2] 的子集腐泻，是否可以推導出 [1,2,3] 的子集呢？先把 [1,2] 的子集寫出來瞅瞅：
[ [],[1],[2],[1,2] ]
你會發(fā)現(xiàn)這樣一個規(guī)律：
subset([1,2,3]) - subset([1,2])
= [3],[1,3],[2,3],[1,2,3]
而這個結(jié)果队询，就是把 sebset([1,2]) 的結(jié)果中每個集合再添加上 3派桩。
換句話說，如果 A = subset([1,2]) 蚌斩，那么：
subset([1,2,3])
= A + [A[i].add(3) for i = 1..len(A)]
這就是一個典型的遞歸結(jié)構(gòu)嘛铆惑，[1,2,3] 的子集可以由 [1,2] 追加得出，[1,2] 的子集可以由 [1] 追加得出送膳，base case 顯然就是當輸入集合為空集時员魏，輸出子集也就是一個空集。
翻譯成代碼就很容易理解了：
vector<vector<int>> subsets(vector<int>& nums) { // base case叠聋，返回一個空集 if (nums.empty()) return {{}}; // 把最后一個元素拿出來 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;}
這個問題的時間復雜度計算比較容易坑人撕阎。我們之前說的計算遞歸算法時間復雜度的方法，是找到遞歸深度碌补，然后乘以每次遞歸中迭代的次數(shù)虏束。對于這個問題，遞歸深度顯然是 N厦章，但我們發(fā)現(xiàn)每次遞歸 for 循環(huán)的迭代次數(shù)取決于 res 的長度镇匀，并不是固定的。
根據(jù)剛才的思路袜啃，res 的長度應該是每次遞歸都翻倍汗侵，所以說總的迭代次數(shù)應該是 2^N∧抑瑁或者不用這么麻煩晃择，你想想一個大小為 N 的集合的子集總共有幾個？2^N 個對吧也物，所以說至少要對 res 添加 2^N 次元素宫屠。
那么算法的時間復雜度就是 O(2^N) 嗎？還是不對滑蚯，2^N 個子集是 push_back 添加進 res的浪蹂，所以要考慮 push_back 這個操作的效率：
vector<vector<int>> res = ...for (int i = 0; i < size; i++) { res.push_back(res[i]); // O(N) res.back().push_back(n); // O(1)}
因為 res[i] 也是一個數(shù)組呀垮耳，push_back 是把 res[i] copy 一份然后添加到數(shù)組的最后圆凰，所以一次操作的時間是 O(N)邑遏。
綜上缓醋，總的時間復雜度就是 O(N*2^N)，還是比較耗時的旭蠕。
空間復雜度的話吗购，如果不計算儲存返回結(jié)果所用的空間的喊递，只需要 O(N) 的遞歸堆棸探＃空間滑绒。如果計算 res 所需的空間闷堡，應該是 O(N*2^N)。
第二種通用方法就是回溯算法疑故。舊文「回溯算法詳解」寫過回溯算法的模板：
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); // 注意 i 從 start 開始遞增 for (int i = start; i < nums.size(); i++) { // 做選擇 track.push_back(nums[i]); // 回溯 backtrack(nums, i + 1, track); // 撤銷選擇 track.pop_back(); }}
可以看見杠览，對 res 的更新是一個前序遍歷，也就是說踱阿，res 就是樹上的所有節(jié)點：
二、組合
輸入兩個數(shù)字 n, k栽烂，算法輸出 [1..n] 中 k 個數(shù)字的所有組合腺办。
vector<vector<int>> combine(int n, int k);
比如輸入 n = 4, k = 2，輸出如下結(jié)果书妻，順序無所謂，但是不能包含重復（按照組合的定義躲履，[1,2] 和 [2,1] 也算重復）：
[
[1,2],
[1,3],
[1,4],
[2,3],
[2,4],
[3,4]
]
這就是典型的回溯算法，k 限制了樹的高度篷帅，n 限制了樹的寬度，直接套我們以前講過的回溯算法模板框架就行了：
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) { // 到達樹的底部 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ù)和計算子集的差不多，區(qū)別在于回季，更新 ****res 的地方是樹的底端掉房。
三诅病、排列
輸入一個不包含重復數(shù)字的數(shù)組 nums芥永，返回這些數(shù)字的全部排列。
vector<vector<int>> permute(vector<int>& nums);
比如說輸入數(shù)組 [1,2,3]棘催，輸出結(jié)果應該如下，順序無所謂呼猪，不能有重復：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
回溯算法詳解 中就是拿這個問題來解釋回溯模板的轴踱。這里又列出這個問題嘁傀，是將「排列」和「組合」這兩個回溯算法的代碼拿出來對比笑撞。
首先畫出回溯樹來看一看：
我們當時使用 Java 代碼寫的解法：
List<List<Integer>> res = new LinkedList<>();/* 主函數(shù)，輸入一組不重復的數(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]); // 進入下一層決策樹 backtrack(nums, track); // 取消選擇 track.removeLast(); }}
回溯模板依然沒有變坚踩，但是根據(jù)排列問題和組合問題畫出的樹來看，排列問題的樹比較對稱瓤狐，而組合問題的樹越靠右節(jié)點越少瞬铸。
在代碼中的體現(xiàn)就是，排列問題每次通過 contains 方法來排除在 track 中已經(jīng)選擇過的數(shù)字础锐；而組合問題通過傳入一個 start 參數(shù)嗓节，來排除 start 索引之前的數(shù)字。
以上皆警，就是排列組合和子集三個問題的解法拦宣，總結(jié)一下：
子集問題可以利用數(shù)學歸納思想，假設已知一個規(guī)模較小的問題的結(jié)果信姓，思考如何推導出原問題的結(jié)果鸵隧。也可以用回溯算法，要用 start 參數(shù)排除已選擇的數(shù)字财破。
組合問題利用的是回溯思想掰派，結(jié)果可以表示成樹結(jié)構(gòu)从诲，我們只要套用回溯算法模板即可左痢，關鍵點在于要用一個 start 排除已經(jīng)選擇過的數(shù)字。
排列問題是回溯思想系洛，也可以表示成樹結(jié)構(gòu)套用算法模板俊性，不同之處在于使用 contains 方法排除已經(jīng)選擇的數(shù)字，前文有詳細分析描扯，這里主要是和組合問題作對比定页。
對于這三個問題，關鍵區(qū)別在于回溯樹的結(jié)構(gòu)绽诚，不妨多觀察遞歸樹的結(jié)構(gòu)典徊，很自然就可以理解代碼的含義了。
