20220505

组合总和

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
k为数字个数  n为和
只使用数字1到9
每个数字 最多使用一次

// 解题思路：因为每个数字最多使用一次，故需要i=start
var combinationSum3 = function(k, n) {
    let ret = []
    let isVaild = (k, sum) => {
        if(sum == n &&path.length==k) return true
        return false
    }

    const dfs = (start, sum=0, path=[]) => {
       if(sum > n) return
       if(sum == n && path.length==k)  ret.push(path)
      for(let i = start;i<=9;i++) {
          dfs(i+1, i+sum, [...path, i])
      }
    }
    dfs(1)

    return ret
};