77.Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Example 2:

Input: n = 1, k = 1
Output: [[1]]

Constraints:

• 1 <= n <= 20
• 1 <= k <= n

analyze

n: 1, 2, 3, 4 k: 2

• 1
  • 2
  • 3
  • 4
• 2
  • 3
  • 4
• 3
  • 4

组合问题中, 不同顺序的解为同一个。比如 [1, 2], [2, 1] 为相同解。

此外可以发现规律, 保留所有增序排列的解即为组合的解。

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
  const result = []
  backTrace(n, k, 1, [], result)
  return result
};

var backTrace = function(n, k, index, temp, result) {
  if (temp.length === k) {
    if (ifIncrease(temp)) {
      result.push([...temp])
    }
    return
  }

  for (let i = index; i <= n; i++) {
    temp.push(i)
    backTrace(n, k, index + 1, temp, result)
    temp.pop()
  }
}

var ifIncrease = function(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] >= arr[i + 1]) return false
  }
  return true
}

提交, 此时报超时的错误。经排查发现, 截支的地方存在问题, 当前在 temp 中的值被重复使用了。修改如下

- backTrace(n, k, index + 1, temp, result)
+ backTrace(n, k, i + 1, temp, result)

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
  const result = []
  backTrace(n, k, 1, [], result)
  return result
};

var backTrace = function(n, k, index, temp, result) {
  if (temp.length === k) {
    result.push([...temp])
    return
  }

  for (let i = index; i <= n; i++) {
    temp.push(i)
    backTrace(n, k, i + 1, temp, result)
    temp.pop()
  }
}

回溯法剪支

还是以 n = 5, k = 3 为例, 上述代码中, 实际遍历的顺序如下:

* 1
  * 2
    * 3
    * 4
    * 5
  * 3
    * 4
    * 5
  * 4
    * 5
  * 5 // 减支
* 2
  * 3
    * 4
    * 5
  * 4
    * 5
  * 5 // 减支
* 3
  * 4
    * 5
  * 5 // 减支
* 4 // 减支

此时, 当第一列的值到达 3 时, 达到搜索上界, [3, 4, 5] 是其中一个解。如果再往后遍历, 4 作为解的开头, 则位数达不到 3 位, 不满足要求了。同理第二列的搜索上界为 4。第三列的搜索上界为 5。接着结合代码进行优化:

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
  const result = []
  backTrace(n, k, 1, [], result)
  return result
};

var backTrace = function(n, k, index, temp, result) {
  if (temp.length === k) {
    result.push([...temp])
    return
  }

  // 题目可以转化为从搜索上界到 n 中要取的数字长度为 (k - temp.length)。
  // 可以得出搜索上界为: n - (k - temp.length) + 1
  for (let i = index; i <= n - (k - temp.length) + 1; i++) {
    temp.push(i)
    backTrace(n, k, i + 1, temp, result)
    temp.pop()
  }
}