1. 题目描述
给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
2. 实现思路
这道题目运用到了普通的回溯剪枝以及深度优先遍历。
原本应该是这样的:
我们可以看到,里面有很多的重复项,所以可以对其进行剪枝操作,即每次递归时开始数+1,剪枝之后就变成了这样:
然后继续进行递归操作,当保存路径的数组的长度和k相等是就将结果保存在结果中,并进行回溯操作。
3. 代码实现
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
let res = []
// start是路径初始值,arr是保存路径节点的数组
const dfs = (start, arr) => {
if(arr.length === k){
res.push([...arr]) // 数组是引用类型,所以要进行一下拷贝
return
}
// 列举所有的选择
for(let i = start; i <= n; i++){
arr.push(i) // 选中元素
dfs(i+1, arr) // 向下继续遍历选择
arr.pop() // 将元素出数组,便于后面进行回溯
}
}
dfs(1, [])
return res
};