-
Notifications
You must be signed in to change notification settings - Fork 0
/
combination-sum.js
80 lines (76 loc) · 1.79 KB
/
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
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
//
// The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
//
// It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
//
//
// Example 1:
//
//
// Input: candidates = [2,3,6,7], target = 7
// Output: [[2,2,3],[7]]
// Explanation:
// 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
// 7 is a candidate, and 7 = 7.
// These are the only two combinations.
//
//
// Example 2:
//
//
// Input: candidates = [2,3,5], target = 8
// Output: [[2,2,2,2],[2,3,3],[3,5]]
//
//
// Example 3:
//
//
// Input: candidates = [2], target = 1
// Output: []
//
//
// Example 4:
//
//
// Input: candidates = [1], target = 1
// Output: [[1]]
//
//
// Example 5:
//
//
// Input: candidates = [1], target = 2
// Output: [[1,1]]
//
//
//
// Constraints:
//
//
// 1 <= candidates.length <= 30
// 1 <= candidates[i] <= 200
// All elements of candidates are distinct.
// 1 <= target <= 500
//
//
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
function combinationSum(candidates, target) {
var buffer = [];
var result = [];
search(0, target);
return result;
function search(startIdx, target) {
if (target === 0) return result.push(buffer.slice());
if (target < 0) return;
for (let i = startIdx; i < candidates.length; i++) {
buffer.push(candidates[i]);
search(i, target - candidates[i]);
buffer.pop();
}
}
}