Skip to content

Commit a703561

Browse files
authored
Merge pull request vJechsmayr#149 from ongzx/combinationSum
Add combination sum js algo
2 parents 7ba9b69 + e163897 commit a703561

2 files changed

Lines changed: 40 additions & 1 deletion

File tree

‎Backtracking/Algorithms_ToDo.md‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,5 @@
44
+ Regular Expression Matching [LeetCode #10](https://leetcode.com/problems/regular-expression-matching/)
55
+ Letter Combination of a Phone Number [LeetCode #17](https://leetcode.com/problems/letter-combinations-of-a-phone-number/)
66
+ Generate Parentheses [LeetCode #22](https://leetcode.com/problems/generate-parentheses/)
7-
+ Combination Sum [LeetCode #39](https://leetcode.com/problems/combination-sum/)
87
+ Wildcard Matching [LeetCode #44](https://leetcode.com/problems/wildcard-matching/)
98
+ N-Queens [LeetCode #51](https://leetcode.com/problems/n-queens/)

‎Backtracking/CombinationSum.js‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/**
2+
* @param {number[]} candidates
3+
* @param {number} target
4+
* @return {number[][]}
5+
*/
6+
var combinationSum = function(candidates, target) {
7+
var result = [];
8+
9+
if (candidates == null || candidates.length === 0) {
10+
return result;
11+
};
12+
13+
var current = [];
14+
candidates.sort();
15+
16+
combinationSumHelper(candidates, target, 0, current, result);
17+
18+
return result;
19+
};
20+
21+
function combinationSumHelper(candidates, target, j, curr, result){
22+
if(target === 0){
23+
var temp = curr.slice();
24+
result.push(temp);
25+
return;
26+
}
27+
28+
for(var i=j; i<candidates.length; i++){
29+
if(target < candidates[i]) {
30+
return;
31+
}
32+
curr.push(candidates[i]);
33+
combinationSumHelper(candidates, target - candidates[i], i, curr, result);
34+
curr.pop();
35+
}
36+
}
37+
38+
const candidates = [2,3,6,7];
39+
const target = 7;
40+
console.log(combinationSum(candidates, target));

0 commit comments

Comments
 (0)