题目描述
给定两个整数 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); } };