77. Combinations

Leetcode link

题目简介

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */

题目给我们一个数字 n 与数字 k

要求我们求出在 1～n 的范围中，长度为 k 的数字组合有多少种

返回所有的数字组合

解题思路

这题很适合用 backtrack 来做

我们只需要注意在循环中 backtrack 后 pop 元素即可

Javascript

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function (n, k) {
    const res = []

    const backtrack = (start, arr) => {
        if (arr.length === k) {
            res.push([...arr])
            return
        }

        for (let i = start; i <= n; i++) {
            arr.push(i)
            backtrack(i + 1, arr)
            arr.pop()
        }
    }

    backtrack(1, [])
    return res
};

复杂度分析

时间

生成不同组合的复杂度为

找到符合要求的组合是，需要复制给 res，复制的复杂度为 O(k)

空间

包含 res 数组：

不包含：O(k)（backtrack 最多 k 层、arr 长度最高为 k）