给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

思路

  1. 递归，列出所有组合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var combine = function (n, k) {
  const result = []
  const handler = (items, curIndex) => {
    if (items.length === k) {
      result.push(items)
      return
    }
    if (curIndex > n) {
      return
    }
    handler([...items], curIndex + 1)
    handler([...items, curIndex], curIndex + 1)
  }
  handler([], 1)
  return result
}

改进思路

  1. 模拟数字递增的结果输出
  2. 实现 incItems 方法，而后枚举添加到结果中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var combine = function (n, k) {
  const incItems = (items) => {
    items = [...items]
    let keyIndex = items.length - 1
    while (keyIndex >= 0 && items[keyIndex] + (items.length - 1 - keyIndex) >= n) {
      --keyIndex
    }
    if (keyIndex < 0) {
      return null
    }
    ++items[keyIndex]
    for (let j = keyIndex + 1; j < items.length; ++j) {
      items[j] = items[j - 1] + 1
    }
    return items
  }
  const result = []
  let keyItems = new Array(k).fill(null).map((_, index) => index + 1)
  while (keyItems) {
    result.push(keyItems)
    keyItems = incItems(keyItems)
  }
  return result
}