31_回溯_77. 组合.md

-- 回溯 - mid 点击直达力扣

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

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

示例 1：

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

// 回溯 + 剪枝
let path = []
let result = []
function combine(n: number, k: number): number[][] {
    result = []
    backTracking(n, k, 1)
    return result
};

function backTracking(n, k, startIndex: number) {
    if (path.length === k) {
        // 注意这里不能直接使用 push(path) ,否则为浅拷贝，
        // 下面 for 循环对 path 的操作会影响 result 的结果集。
        result.push([...path]);
        return;
    }

    // 扩容，为了取到最右边的元素，故将范围扩到n+1，
    // 但我们不需要 n+1，所以将其 return
    // for (let i = startIndex; i <= n + 1; i++) {
    //     if (i === n + 1) { return }

    // 剪枝
    // k - path.length 为剩余要push进path的长度
    // n - (k - path.length) 为每层for循环最多要遍历到哪个位置
    // +1 时因为我们的下标是从1开始的,而不是0开始
    for (let i = startIndex; i <= n - (k - path.length) + 1; i++) {
        path.push(i)
        backTracking(n, k, i + 1)  // 递归
        path.pop()     // 回溯
    }
}