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

## 示例

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

## 题解

```javascript
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    if(n <= k) return [[...new Array(n).keys()].map(v => v+1)];
    var target = [];
    var dfs = function(cur, deep, tmp){
        if (tmp.length + (n - cur + 1) < k) return void 0;
        if(deep === k){
            target.push(tmp);
            return void 0;
        }
        for(;cur<=n;++cur) dfs(cur+1, deep+1, [...tmp, cur]);
    }
    dfs(1, 0, []);
    return target;
};
```

## 思路
以示例中的值为例，可以认为是一个长度为`4`的数组`[1, 2, 3, 4]`，每两个组合一个数组可取`1`组合其数组中之后的值，`2`与其数组中之后值，`3`与其数组中之后的值，`4`与其数组中之后值，即`[1, 2]`、`[1, 3]`、`[1, 4]`、`[2, 3]`、`[2, 4]`、`[3, 4]`，首先初始条件判断，若是`n <= k`则只能构成一个长度为`n`的数组，将其装入二维数组返回即可，后边的表达式利用了`new Array(n)`生成了一个长度为`n`的空数组，让后取得其`keys`的迭代器，利用`...`即`Spread`操作符将其展开，之后使用`map`将其处理为`key`值`+1`，之后定义目标数组，之后定义`dfs`递归函数，首先进行剪枝，如果当前`tmp`数组的大小为`s`，未确定状态的区间`[cur,n]`的长度为`t`，如果`s + t < k`，那么即使`t`个都被选中，也不可能构造出一个长度为`k`的序列，故这种情况就没有必要继续向下递归，之后判断递归深度如果与`k`相等则直接将`tmp`数组置入目标数组并返回，之后定义一个循环，从`cur`开始到`n`进行递归取值，将`tmp`数组与`cur`构建一个新数组传递到下一个递归中，之后启动递归初始化`cur`为`1`，深度`deep`为`0`，`tmp`为一个空数组，递归完成后返回目标数组即可。



## 每日一题

```
https://github.com/WindrunnerMax/EveryDay
```

## 参考

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