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 result = [];

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

    for (let i = begin; i <= 9; i++) {
      if (sum < n) {
        track.push(i);
        dfs(i + 1, sum + i, track.slice());
        track.pop();
      }
    }
  };

  dfs(1, 0, []);
  return result;
};