0077._Combinations

发表于 分类于 ， ，

077. Combinations

难度: Medium

刷题内容

原题连接

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],
 ]

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解题方案

思路
**- 时间复杂度: O(Nlogn)**- 空间复杂度: O(N)**

回溯算法，算法参考：leetCode回溯算法+剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */

var combine = function(n, k) {
  const result = []
  if (n <= 0 || k <= 0 || n < k) {
    return result;
  }
  findCombinations(n, k, 1, [])
  function findCombinations(n, k, index, list) {
    list = [...list]
    if (list.length === k) {
      result.push(list);
      return;
    }
    for (let i = index; i <= n - (k - list.length) + 1; i++) {
      list.push(i);
      findCombinations(n, k, i + 1, list);
      list.pop();
    }
  }
  
  return result
};