子集排列组合

今天就来聊三道考察频率高，而且容易让人搞混的算法问题，分别是求子集（subset），求排列（permutation），求组合（combination）。

这几个问题都可以用回溯算法模板解决，同时子集问题还可以用数学归纳思想解决。读者可以记住这几个问题的回溯套路，就不怕搞不清了。

一、子集

问题很简单，输入一个不包含重复数字的数组，要求算法输出这些数字的所有子集。

  1. 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 显然就是当输入集合为空集时，输出子集也就是一个空集。

翻译成代码就很容易理解了：

  1. vector<vector<int>> subsets(vector<int>& nums) {
  2.     // base case，返回一个空集
  3.     if (nums.empty()) return {{}};
  4.     // 把最后一个元素拿出来
  5.     int n = nums.back();
  6.     nums.pop_back();
  7.     // 先递归算出前面元素的所有子集
  8.     vector<vector<int>> res = subsets(nums);
  10.     int size = res.size();
  11.     for (int i = 0; i < size; i++) {
  12.         // 然后在之前的结果之上追加
  13.         res.push_back(res[i]);
  14.         res.back().push_back(n);
  15.     }
  16.     return res;
  17. }

这个问题的时间复杂度计算比较容易坑人。我们之前说的计算递归算法时间复杂度的方法，是找到递归深度，然后乘以每次递归中迭代的次数。对于这个问题，递归深度显然是 N，但我们发现每次递归 for 循环的迭代次数取决于 res 的长度，并不是固定的。

根据刚才的思路，res 的长度应该是每次递归都翻倍，所以说总的迭代次数应该是 2^N。或者不用这么麻烦，你想想一个大小为 N 的集合的子集总共有几个？2^N 个对吧，所以说至少要对 res 添加 2^N 次元素。

那么算法的时间复杂度就是 O(2^N) 吗？还是不对，2^N 个子集是 push_back 添加进 res 的，所以要考虑 push_back 这个操作的效率：

  1. for (int i = 0; i < size; i++) {
  2.     res.push_back(res[i]); // O(N)
  3.     res.back().push_back(n); // O(1)
  4. }

因为 res[i] 也是一个数组呀，push_back 是把 res[i] copy 一份然后添加到数组的最后，所以一次操作的时间是 O(N)。

综上，总的时间复杂度就是 O(N*2^N)，还是比较耗时的。

空间复杂度的话，如果不计算储存返回结果所用的空间的，只需要 O(N) 的递归堆栈空间。如果计算 res 所需的空间，应该是 O(N*2^N)。

第二种通用方法就是回溯算法。旧文「回溯算法详解」写过回溯算法的模板：

  1. result = []
  2. def backtrack(路径, 选择列表):
  3.     if 满足结束条件:
  4.         result.add(路径)
  5.         return
  6.     for 选择 in 选择列表:
  7.         做选择
  8.         backtrack(路径, 选择列表)
  9.         撤销选择

只要改造回溯算法的模板就行了：

  1. vector<vector<int>> res;
  3. vector<vector<int>> subsets(vector<int>& nums) {
  4.     // 记录走过的路径
  5.     vector<int> track;
  6.     backtrack(nums, 0, track);
  7.     return res;
  8. }
  10. void backtrack(vector<int>& nums, int start, vector<int>& track) {
  11.     res.push_back(track);
  12.     for (int i = start; i < nums.size(); i++) {
  13.         // 做选择
  14.         track.push_back(nums[i]);
  15.         // 回溯
  16.         backtrack(nums, i + 1, track);
  17.         // 撤销选择
  18.         track.pop_back();
  19.     }
  20. }

可以看见，对 res 更新的位置处在前序遍历，也就是说，res 就是树上的所有节点：

子集排列组合 - 图1

二、组合

输入两个数字 n, k，算法输出 [1..n] 中 k 个数字的所有组合。

  1. 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 限制了树的宽度，继续套我们以前讲过的回溯算法模板框架就行了：

子集排列组合 - 图2

  1. vector<vector<int>>res;
  3. vector<vector<int>> combine(int n, int k) {
  4.     if (k <= 0 || n <= 0) return res;
  5.     vector<int> track;
  6.     backtrack(n, k, 1, track);
  7.     return res;
  8. }
  10. void backtrack(int n, int k, int start, vector<int>& track) {
  11.     // 到达树的底部
  12.     if (k == track.size()) {
  13.         res.push_back(track);
  14.         return;
  15.     }
  16.     // 注意 i 从 start 开始递增
  17.     for (int i = start; i <= n; i++) {
  18.         // 做选择
  19.         track.push_back(i);
  20.         backtrack(n, k, i + 1, track);
  21.         // 撤销选择
  22.         track.pop_back();
  23.     }
  24. }

backtrack 函数和计算子集的差不多，区别在于，更新 res 的时机是树到达底端时。

三、排列

输入一个不包含重复数字的数组 nums，返回这些数字的全部排列。

  1. 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] ]

「回溯算法详解」中就是拿这个问题来解释回溯模板的。这里又列出这个问题，是将「排列」和「组合」这两个回溯算法的代码拿出来对比。

首先画出回溯树来看一看：

子集排列组合 - 图3

我们当时使用 Java 代码写的解法： labuladong 提供Java解法代码：

  1. List<List<Integer>> res = new LinkedList<>();
  3. /* 主函数，输入一组不重复的数字，返回它们的全排列 */
  4. List<List<Integer>> permute(int[] nums) {
  5.     // 记录「路径」
  6.     LinkedList<Integer> track = new LinkedList<>();
  7.     backtrack(nums, track);
  8.     return res;
  9. }
  11. void backtrack(int[] nums, LinkedList<Integer> track) {
  12.     // 触发结束条件
  13.     if (track.size() == nums.length) {
  14.         res.add(new LinkedList(track));
  15.         return;
  16.     }
  18.     for (int i = 0; i < nums.length; i++) {
  19.         // 排除不合法的选择
  20.         if (track.contains(nums[i]))
  21.             continue;
  22.         // 做选择
  23.         track.add(nums[i]);
  24.         // 进入下一层决策树
  25.         backtrack(nums, track);
  26.         // 取消选择
  27.         track.removeLast();
  28.     }
  29. }

renxiaoyao 提供C++解法代码：

  1. class Solution {
  2. public:
  3.     vector<vector<int>> permute(vector<int>& nums) {
  4.         paths.clear();
  5.         path.clear();
  7.         vector<int> used(nums.size(),false);
  9.         helper(nums,used);
  11.         return paths;
  12.     }
  13. private:
  14.     void helper(vector<int>& nums,vector<int>& used) {
  15.         if(path.size() == nums.size()) {
  16.             paths.push_back(path);
  17.             return ;
  18.         }
  20.         for(int i = 0 ; i < nums.size() ; ++i) {
  21.             if(used[i]) continue;
  23.             used[i] = true;
  24.             path.push_back(nums[i]);
  26.             helper(nums,used);
  28.             path.pop_back();
  29.             used[i] = false;
  30.         }
  31.     }
  32. private:
  33.     vector<vector<int>> paths;
  34.     vector<int> path;
  35. };

回溯模板依然没有变，但是根据排列问题和组合问题画出的树来看，排列问题的树比较对称，而组合问题的树越靠右节点越少。

在代码中的体现就是，排列问题每次通过 contains 方法来排除在 track 中已经选择过的数字；而组合问题通过传入一个 start 参数，来排除 start 索引之前的数字。

以上，就是排列组合和子集三个问题的解法，总结一下：

子集问题可以利用数学归纳思想，假设已知一个规模较小的问题的结果，思考如何推导出原问题的结果。也可以用回溯算法，要用 start 参数排除已选择的数字。

组合问题利用的是回溯思想，结果可以表示成树结构，我们只要套用回溯算法模板即可，关键点在于要用一个 start 排除已经选择过的数字。

排列问题是回溯思想，也可以表示成树结构套用算法模板，关键点在于使用 contains 方法排除已经选择的数字，前文有详细分析，这里主要是和组合问题作对比。

记住这几种树的形状，就足以应对大部分回溯算法问题了，无非就是 start 或者 contains 剪枝，也没啥别的技巧了。