Skip to main content

组合总数 III

题目​

找出所有相加之和为 n 的 k 个数的组合. 组合中只允许含有 1 - 9 的正整数, 并且每种组合中不存在重复的数字.

说明:

  • 所有数字都是正整数
  • 解集不能包含重复的组合
示例
输入: k = 3, n = 7

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

输出: [
  [1, 2, 6],
  [1, 3, 5],
  [2, 3, 4],
]

题解​

好了我已经吐了, 回溯, 回溯, 回溯.

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function (k, n) {
  const res = []

  const dfs = (begin, track, sum) => {
    if (track.length === k && sum === n) {
      res.push(track.slice())
      return
    }

    for (let i = begin; i < 10; i++) {
      if (sum < n && !track.includes(i)) {
        track.push(i)
        dfs(i, track, sum + i)
        track.pop()
      }
    }
  }

  dfs(1, [], 0)

  return res
}