组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字最多使用一次

返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

1
2
3
4
5

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    let ans = []
    let path = []
    let sum = 0

    function dfs(startNum) {
        if(path.length === k) {
            if(sum === n) {
                ans.push([...path])
            }
            return 
        }

        for(let i = startNum; i <= 9; i++) {
            path.push(i)
            sum += i

            dfs(i + 1)

            sum -= path.pop()
        }
    }

    dfs(1)

    return ans
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

← 反转链表存在重复元素→