# 077. Combinations

**<font color=red>难度: Medium</font>**

## 刷题内容

> 原题连接

[https://leetcode-cn.com/problems/combinations/](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回溯算法+剪枝](https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/)

```javascript
/**
 * @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
};
```