力扣小白刷题之77题组合

题目描述

给定两个整数 n 和 k，返回 1…n 中所有可能的 k 个数的组合。
返回结果的顺序无所谓，但是不能包含重复(按照组合定义，[1, 2] 和 [2, 1] 也算重复)。

分析

回溯算法
k 限制了树的高度， n 限制了树的宽度
关键：

1. 画图，清晰地展现递归结构，按顺序取就无需使用 used 数组判断是否取过
2. 在 树的第 k 层进行结算，因此 combineList 的长度是需要关注的
3. 需要剪枝
   
   图中绿色的部分，是不能产生结果的分支，需要剪掉。
   for循环中，剪枝前条件for(int i = start; i <= n; i++)，for循环中干的事情，是从 [i, n] 这个区间里，找到 k - combineList.size() 个元素， i <= n 不是每次都要走完的，i 由一个上限。
   寻找规律：
   
   可以发现，max(i) 与接下来要选择的元素貌似有一点关系，很容易可以知道：
   max(i) + 接下来要选择的元素个数 - 1 = n，其中，接下来要选择的元素个数 = k - combineList.size()，整理得到：
   max(i) = n - (k - combineList.size()) + 1
   所以，剪枝的过程就是把 i <= n 换成 i <= n - (k - combineList.size()) + 1。

代码

当使用 k - 1进行递归时，代码如下：