组合总和-216

力扣（LeetCode） 链接：https://leetcode.cn/problems/combination-sum-iii/

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

  function bfs(start, sum) {
    if (sum === n && path.length === k) {
      res.push([...path])
      return
    }
    for (let i = start; n - sum >= i && 9 - (k - path.length) + 1 >= i; i++) {
      path.push(i)
      bfs(i + 1, sum + i)
      path.pop()
    }
  }

  bfs(1, 0)
  return res
}