77. 组合

https://leetcode-cn.com/problems/combinations/

题目描述

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combinations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

DFS

• 递归枚举所有组合。

• 对一个数字，有选和不选两种可能，做出选择后，再递归地对后面的数字进行选择。

剪枝

在递归解法的基础上还可以做一些剪枝的优化。

比如如果剩下的数字加上临时数组里面的数字个数小于 k，那这个解就可以提前放弃了。

// prune
var leftNums = n - cur + 1;
if (leftNums < k - arr.length) return;

复杂度分析

• 时间复杂度：$O()$。TODO

• 空间复杂度：$O(n)$，调用栈的高度是 $O(n)$，临时数组的长度是 $O(k)$。

代码

JavaScript Code

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

    // **********************

    function dfs(cur, arr) {
        if (arr.length === k) {
            res.push([...arr]);
            return;
        }
        if (cur > n) return;

        // prune
        var leftNums = n - cur + 1;
        if (leftNums < k - arr.length) return;

        // pick
        arr.push(cur);
        dfs(cur + 1, arr);

        // not pick
        arr.pop();
        dfs(cur + 1, arr);
    }
};