leetcode/algorithms/CombinationSum/solution.js at master · P-ppc/leetcode · 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
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    let res = [],
        t = []
    backTrack(candidates, [], target, res)
    res.forEach(s => {
        t.push(s.split(',').map(d => parseInt(d)))
    })
    return t
};

var backTrack = function(candidates, ans, target, res) {
    if (target === 0) {
        ans.sort()
        let s = ans.join(',')
        if (res.findIndex(d => d === s) === -1) {
            res.push(s)
        }
    } else {
        candidates.forEach(c => {
            if (c <= target) {
                let temp = ans.slice(0)
                temp.push(c)
                backTrack(candidates, temp, target - c, res)
            }
        })
    }
};