forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0039-combination-sum.js
26 lines (22 loc) · 867 Bytes
/
0039-combination-sum.js
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
/**
* https://leetcode.com/problems/combination-sum/
* Time O(N * ((Target/MIN) + 1)) | Space O(N * (Target/Min))
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target, index = 0, combination = [], combinations = []) {
const isBaseCase = target < 0;
if (isBaseCase) return combinations;
const isTarget = target === 0;
if (isTarget) return combinations.push(combination.slice());
for (let i = index; i < candidates.length; i++) {
backTrack(candidates, target, i, combination, combinations);
}
return combinations;
}
const backTrack = (candidates, target, i, combination, combinations) => {
combination.push(candidates[i]);
combinationSum(candidates, (target - candidates[i]), i, combination, combinations);
combination.pop();
}