216. 组合总和 III

1. 题目描述

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

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。

示例 1:

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

示例 2:

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

2. 解题思路

和39、40题思路一样。

3. 代码实现

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    const res = []
    const dfs = (start, arr, sum) => {
        if(arr.length === k){
            if(sum === n){
                res.push([...arr])
            }
            return
        }
        for(let i = start; i <= 9; i++){
            arr.push(i)
            dfs(i + 1, arr, sum + i)
            arr.pop()
        }
    }
    dfs(1, [], 0)
    return res
};

4. 提交结果