leetcode-javascript/combination-sum-iii.js at master · didi0613/leetcode-javascript · GitHub

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function (k, n) {
    var numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    var ret = [];
    helper(numbers, ret, k, n, [], 0);
    return ret;
};

function helper(numbers, ret, k, target, item, index) {
    if (target < 0 || item.length > k) {
        return;
    }

    if (target === 0 && item.length === k) {
        ret.push(item.slice());
    }

    for (var i = index; i < numbers.length; i++) {
        item.push(numbers[i]);
        helper(numbers, ret, k, target - numbers[i], item, i + 1);
        item.pop();
    }
}

// Similar Solution
/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function (k, n) {
    var ret = [];
    combinationSum3Builder(k, n, ret, [], 1);
    return ret;
};

function combinationSum3Builder(k, n, ret, item, index) {
    if (item.length > k || n < 0) {
        return;
    }

    if (n === 0 && item.length === k) {
        ret.push(item.slice());
    }

    for (var i = index; i <= 9; i++) {
        item.push(i);
        combinationSum3Builder(k, n - i, ret, item, i + 1);
        item.pop();
    }
}