题目地址(77. 组合)

https://leetcode-cn.com/problems/combinations/

题目描述

  1. 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
  3. 你可以按 任何顺序 返回答案。
  7. 示例 1：
  9. 输入：n = 4, k = 2
  10. 输出：
  11. [
  12.   [2,4],
  13.   [3,4],
  14.   [2,3],
  15.   [1,2],
  16.   [1,3],
  17.   [1,4],
  18. ]
  20. 示例 2：
  22. 输入：n = 1, k = 1
  23. 输出：[[1]]
  27. 提示：
  29. 1 <= n <= 20
  30. 1 <= k <= n

前置知识


公司

  • 暂无

思路

溯法解决的问题都可以抽象为树形结构（N叉树），用树形结构来理解回溯就容易多了

回溯法三部曲

  • 递归函数的返回值以及参数

在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
然后还需要一个参数，为int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,…,n] ）。
为什么要有这个startIndex呢？
每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex。
从下图中红线部分可以看出，在集合[1,2,3,4]取1之后，下一层递归，就要在[2,3,4]中取数了，那么下一层递归如何知道从[2,3,4]中取数呢，靠的就是startIndex
image.png
所以需要startIndex来记录下一层递归，搜索的起始位置。

  • 回溯函数终止条件

什么时候到达所谓的叶子节点了呢？
path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。

  • 单层搜索的过程

回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。
image.png
for循环每次从startIndex开始遍历，然后用path保存取到的节点i。
可以看出backtracking（递归函数）通过不断调用自己一直往深处遍历，总会遇到叶子节点，遇到了叶子节点就要返回。
backtracking的下面部分就是回溯的操作了，撤销本次处理的结果。

剪枝优化

来举一个例子，n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。 在第二层for循环，从元素3开始的遍历都没有意义了。
image.png
图中每一个节点（图中为矩形），就代表本层的一个for循环，那么每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。
所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了
优化过程如下：

  1. 已经选择的元素个数：path.size();
  2. 还需要的元素个数为: k - path.size();
  3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
从2开始搜索都是合理的，可以是组合[2, 3, 4]。

关键点


代码

  • 语言支持：Java

Java Code:

  1. class Solution {
  2.         //返回数组
  3.         ArrayList<List<Integer>> res = new ArrayList<>();
  4.         //单个路径的数组
  5.         LinkedList<Integer> path = new LinkedList<>();
  6.         public List<List<Integer>> combine(int n, int k) {
  7.             //每个数字都是从1开始
  8.             loop(1, n, k);
  9.             return res;
  10.         }
  12.         void loop(int startIndex, int n, int k) {
  13.             //如果当前路径的长度=需要的长度 就将路径添加到返回数组中
  14.             if (path.size() == k) {
  15.                 res.add(new ArrayList<>(path));
  16.                 return;
  17.             }
  18.             //横向遍历 从1开始 1 ->2 3 4 然后是 2 -> 34 ...
  19.             //这里如果是 i <= n 的话 会多出很多没用的递归 这时候需要剪枝
  20.             //path.size()是取了多少个数字 k - path.size()为当前还能取多少个数字
  21.             //i <= n - (k - path.size()) + 1为 最多遍历到这个位置
  22.             for (int i = startIndex; i <= n - (k - path.size()) + 1 ; i++) {
  23.                 //将每次循环的i添加到组合中
  24.                 path.add(i);
  25.                 //纵向遍历 每次把开始值+1
  26.                 loop(i+1, n, k);
  27.                 //递归完直到有返回值的时候就把最后一个数移除 比如输出了 1,2 移除2 再继续递归下一个 1,3 ...1,4
  28.                 path.removeLast();
  29.             }
  30.         }
  31.     }

剪枝前14ms 超54
剪枝后 1ms 超99
复杂度分析

令 n 为数组长度。

  • 时间复杂度：77. 组合 - 图4#card=math&code=O%28n%29&id=ndVNS)
  • 空间复杂度：77. 组合 - 图5#card=math&code=O%28n%29&id=PrlGa)