讀完本文，你可以去力扣拿下如下題目：

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 剪枝，也沒啥別的技巧了。