目录
题目来源
题目描述
给定两个整数?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 <= 201 <= 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()
}
}