概述
题目描述
给定两个整数 n 和 k，返回 1…n 中所有可能的 k 个数的组合。
返回结果的顺序无所谓，但是不能包含重复(按照组合定义，[1, 2] 和 [2, 1] 也算重复)。
分析
回溯算法
k 限制了树的高度， n 限制了树的宽度
关键：
- 画图，清晰地展现递归结构，按顺序取就无需使用 used 数组判断是否取过
- 在 树的第 k 层进行结算，因此 combineList 的长度是需要关注的
- 需要剪枝
图中绿色的部分，是不能产生结果的分支，需要剪掉。
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进行递归时，代码如下：
最后
以上就是称心黄蜂为你收集整理的力扣小白刷题之77题组合的全部内容，希望文章能够帮你解决力扣小白刷题之77题组合所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复