216. Combination Sum III

[Tcdian]

216. Combination Sum III

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

说明：

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

Example 1

Input: k = 3, n = 7
Output: [[1,2,4]]

Example 2

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    const reuslt = [];
    const part = [];
    backtracking(1);
    return reuslt;

    function backtracking(index) {
        const sum = part.reduce((prev, current) => prev + current, 0);
        if (sum >= n || part.length >= k) {
            if (sum === n && part.length === k) {
                reuslt.push([...part]);
            }
            return;
        }
        for (let i = index; i <= 9; i++) {
            part.push(i);
            backtracking(i + 1);
            part.pop();
        }
    }
};

• TypeScript Solution

function combinationSum3(k: number, n: number): number[][] {
    const reuslt: number[][] = [];
    const part: number[] = [];
    backtracking(1);
    return reuslt;

    function backtracking(index: number) {
        const sum = part.reduce((prev, current) => prev + current, 0);
        if (sum >= n || part.length >= k) {
            if (sum === n && part.length === k) {
                reuslt.push([...part]);
            }
            return;
        }
        for (let i = index; i <= 9; i++) {
            part.push(i);
            backtracking(i + 1);
            part.pop();
        }
    }
}