组合 -77
介绍
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例：
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]理解
一种暴力解法：有几个数就使用几次 for 循环。k 次就使用 k 次 for 循环，但仅限于已知 k 的情况。
所以需要利用到回溯算法。回溯算法解决的问题可以抽象为一个树形结构。
代码
ts
function traverseNK (n:number, k:number) {
// 最终返回的结果
const res = [] as number[][]
function helper (startNumber: number, pre: number[]) {
// 如果结果集的长度等于 k，满足题目条件，推入最终返回的结果数组中
if(pre.length === k) {
res.push(pre)
return
}
// 循环的开始索引为传入的开始索引
// 循环条件：剩余的可加入结果集的数字长度大于等于结果集还需要的元素个数
for(let number = startNumber; n - number + 1 >= k - pre.length; number ++) {
helper(number + 1, pre.concat(number))
}
}
// 开始数字为 1，结果集为空数组
helper(1, [])
return res
}
// in-source test suites
if (import.meta.vitest) {
const { it, expect } = import.meta.vitest
it('test', () => {
const res = [
[1,2],
[1,3],
[1,4],
[2,3],
[2,4],
[3,4]
]
expect(traverseNK(4, 2)).toEqual(res)
})
}