目录

题目来源

题目描述

示例

提示

题目解析

算法源码

剪枝优化 

---

题目来源

77. 组合 - 力扣（LeetCode）

题目描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

输入：n = 1, k = 1
输出：[[1]]

提示

• 1 <= n <= 20
• 1 <= k <= n

题目解析

这题就是求组合的问题。

组合和排列的区别在于，组合是无顺序性的，而排列是有顺序性的。

比如在[1,2,3]中任选两个数字的全排列有：

• 12
• 21
• 13
• 31
• 23
• 32

而全组合有：

• 12
• 13
• 23

也就是说，对于组合来说12和21是同一个。

组合的求解也可以模拟为一个树结构

黄色部分是第一层选择完后，剩余可选数。

有人可能有疑问，为什么第一层选完2后，剩余可选数不是13，而是只有3呢？

我们假设第一层选完2后，剩余可选数是13，则

 最终会产生12和21这种重复组合。

因此组合的树结构，单层节点选择时，如果采用for顺序遍历的话，则后面层级节点选择起始位置 要比 前面层级节点选择起始位置 + 1。

比如第一层选择了1，则第二层从2开始选

比如第一层选择了2，则第二层从3开始选

只有这样才能避免重复。

组合由于和排列问题一样也能用树结构模拟，因此也可以用回溯算法，基于递归模型进行实现。

假设，从n个数中选择k个数，每层得到节点保存进path中，则当path.length === k 时，说明已经选择了path中已经保存了k个数，符合结束要求，结束递归。

每层节点选择没有特殊条件的话，即只要保证后面层级节点选择的起始位置，是上一层选择的节点的位置i的后一个，即i+1，这样才能保证无重复的组合。

算法源码

/*** @param {number} n* @param {number} k* @return {number[][]}*/
var combine = function(n, k) {let result = []dfs(n, k, 1, [], result)return result
};function dfs(n, k, index, path, result) {if(path.length === k) {return result.push([...path])}for(let i=index; i<=n; i++) {path.push(i)dfs(n, k, i+1, path, result)path.pop()}
}

剪枝优化 

题目中提示

1 <= k <= n

也就是说存在k===n的情况，比如我从4个数里面取4个，此时很显然只有一种组合，就是1234。但是按照上面算法源码逻辑，我们会出现如下图所示的递归过程

 当第一层取2时，第二层可选数字就只有3了，因此这个分叉的结果为23，由于不满足k=4，因此最终会丢弃。

剪枝优化，指的是，我们可以提前判断某分支是否符合最终要求，若不符合要求，则再其走递归流程前就结束它。

 比如当第一层选取2后，理论上还需要选择k-1=2个元素，但是实际上，第一层选完2后，只能选3了，即只剩余1个元素可选，因此我们不需要走完递归流程，也知道此分支的结果是不符合要求的，因此可以提前结束。

/*** @param {number} n* @param {number} k* @return {number[][]}*/
var combine = function(n, k) {let result = []dfs(n, k, 1, [], result)return result
};function dfs(n, k, index, path, result) {if(path.length === k) {return result.push([...path])}for(let i=index; i<=n; i++) {if(n - i + 1 < k - path.length) break // 剪枝path.push(i)dfs(n, k, i+1, path, result)path.pop()}
}

但是上面代码中的剪枝策略，依旧存在无意义的for循环遍历，循环的结束条件都放到了循环体中，因此可以继续优化

/*** @param {number} n* @param {number} k* @return {number[][]}*/
var combine = function(n, k) {let result = []dfs(n, k, 1, [], result)return result
};function dfs(n, k, index, path, result) {if(path.length === k) {return result.push([...path])}for(let i=index; i<=n-(k-path.length)+1; i++) { // 将剪枝条件整合到循环条件中，减少循环次数path.push(i)dfs(n, k, i+1, path, result)path.pop()}
}