讀完本文，你可以去力扣拿下如下題目：
78.子集
46.全排列
77.組合
-----------
今天就來聊三道考察頻率高，而且容易讓人搞混的演算法問題，分別是求子集（subset），求排列（permutation），求組合（combination）。
這幾個問題都可以用回溯演算法模板解決，同時子集問題還可以用數學歸納思想解決。讀者可以記住這幾個問題的回溯套路，就不怕搞不清了。
一、子集問題很簡單，輸入一個不包含重複數字的陣列，要求演算法輸出這些數字的所有子集。
vector<vector<int>> subsets(vector<int>& nums);比如輸入 nums = [1,2,3]，你的演算法應輸出 8 個子集，包含空集和本身，順序可以不同：
[ [],[1],[2],[3],[1,3],[2,3],[1,2],[1,2,3] ]
第一個解法是利用數學歸納的思想：假設我現在知道了規模更小的子問題的結果，如何推匯出當前問題的結果呢？
具體來說就是，現在讓你求 [1,2,3] 的子集，如果你知道了 [1,2] 的子集，是否可以推匯出 [1,2,3] 的子集呢？先把 [1,2] 的子集寫出來瞅瞅：
[ [],[1],[2],[1,2] ]
你會發現這樣一個規律：
subset([1,2,3]) - subset([1,2])
= [3],[1,3],[2,3],[1,2,3]
而這個結果，就是把 sebset([1,2]) 的結果中每個集合再新增上 3。
換句話說，如果 A = subset([1,2]) ，那麼：
subset([1,2,3])
= A + [A[i].add(3) for i = 1..len(A)]
這就是一個典型的遞迴結構嘛，[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++) { // 然後在之前的結果之上追加 res.push_back(res[i]); res.back().push_back(n); } return res;}這個問題的時間複雜度計算比較容易坑人。我們之前說的計算遞迴演算法時間複雜度的方法，是找到遞迴深度，然後乘以每次遞迴中迭代的次數。對於這個問題，遞迴深度顯然是 N，但我們發現每次遞迴 for 迴圈的迭代次數取決於 res 的長度，並不是固定的。
根據剛才的思路，res 的長度應該是每次遞迴都翻倍，所以說總的迭代次數應該是 2^N。或者不用這麼麻煩，你想想一個大小為 N 的集合的子集總共有幾個？2^N 個對吧，所以說至少要對 res 新增 2^N 次元素。
那麼演算法的時間複雜度就是 O(2^N) 嗎？還是不對，2^N 個子集是 push_back 新增進 res 的，所以要考慮 push_back 這個操作的效率：
for (int i = 0; i < size; i++) { res.push_back(res[i]); // O(N) res.back().push_back(n); // O(1)}因為 res[i] 也是一個數組呀，push_back 是把 res[i] copy 一份然後新增到陣列的最後，所以一次操作的時間是 O(N)。
綜上，總的時間複雜度就是 O(N*2^N)，還是比較耗時的。
空間複雜度的話，如果不計算儲存返回結果所用的空間的，只需要 O(N) 的遞迴堆疊空間。如果計算 res 所需的空間，應該是 O(N*2^N)。
第二種通用方法就是回溯演算法。舊文「回溯演算法詳解」寫過回溯演算法的模板：
result = []def backtrack(路徑, 選擇列表): if 滿足結束條件: 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 就是樹上的所有節點：
二、組合輸入兩個數字 n, k，演算法輸出 [1..n] 中 k 個數字的所有組合。
vector<vector<int>> combine(int n, int k);比如輸入 n = 4, k = 2，輸出如下結果，順序無所謂，但是不能包含重複（按照組合的定義，[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 函式和計算子集的差不多，區別在於，更新 res 的時機是樹到達底端時。
三、排列輸入一個不包含重複數字的陣列 nums，返回這些數字的全部排列。
vector<vector<int>> permute(vector<int>& nums);比如說輸入陣列 [1,2,3]，輸出結果應該如下，順序無所謂，不能有重複：
[ [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<>();/* 主函式，輸入一組不重複的數字，返回它們的全排列 */List<List<Integer>> permute(int[] nums) { // 記錄「路徑」 LinkedList<Integer> track = new LinkedList<>(); backtrack(nums, track); return res;}void backtrack(int[] nums, LinkedList<Integer> track) { // 觸發結束條件 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(); }}回溯模板依然沒有變，但是根據排列問題和組合問題畫出的樹來看，排列問題的樹比較對稱，而組合問題的樹越靠右節點越少。
在程式碼中的體現就是，排列問題每次透過 contains 方法來排除在 track 中已經選擇過的數字；而組合問題透過傳入一個 start 引數，來排除 start 索引之前的數字。
以上，就是排列組合和子集三個問題的解法，總結一下：
子集問題可以利用數學歸納思想，假設已知一個規模較小的問題的結果，思考如何推匯出原問題的結果。也可以用回溯演算法，要用 start 引數排除已選擇的數字。
組合問題利用的是回溯思想，結果可以表示成樹結構，我們只要套用回溯演算法模板即可，關鍵點在於要用一個 start 排除已經選擇過的數字。
排列問題是回溯思想，也可以表示成樹結構套用演算法模板，關鍵點在於使用 contains 方法排除已經選擇的數字，前文有詳細分析，這裡主要是和組合問題作對比。
記住這幾種樹的形狀，就足以應對大部分回溯演算法問題了，無非就是 start 或者 contains 剪枝，也沒啥別的技巧了。