Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb33f1d5

Browse files
committed
Add "Combination Sum" backtracking algorithm.
1 parentb41cffe commitb33f1d5

File tree

4 files changed

+151
-0
lines changed

4 files changed

+151
-0
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -70,6 +70,7 @@ a set of rules that precisely define a sequence of operations.
7070
*`A`[Shortest Common Supersequence](src/algorithms/sets/shortest-common-supersequence) (SCS)
7171
*`A`[Knapsack Problem](src/algorithms/sets/knapsack-problem) - "0/1" and "Unbound" ones
7272
*`A`[Maximum Subarray](src/algorithms/sets/maximum-subarray) - "Brute Force" and "Dynamic Programming" (Kadane's) versions
73+
*`A`[Combination Sum](src/algorithms/sets/combination-sum) - find all combinations that form specific sum
7374
***Strings**
7475
*`A`[Levenshtein Distance](src/algorithms/string/levenshtein-distance) - minimum edit distance between two sequences
7576
*`B`[Hamming Distance](src/algorithms/string/hamming-distance) - number of positions at which the symbols are different
@@ -156,6 +157,7 @@ different path of finding a solution. Normally the DFS traversal of state-space
156157
*`A`[Hamiltonian Cycle](src/algorithms/graph/hamiltonian-cycle) - Visit every vertex exactly once
157158
*`A`[N-Queens Problem](src/algorithms/uncategorized/n-queens)
158159
*`A`[Knight's Tour](src/algorithms/uncategorized/knight-tour)
160+
*`A`[Combination Sum](src/algorithms/sets/combination-sum) - find all combinations that form specific sum
159161
***Branch & Bound** - remember the lowest-cost solution found at each stage of the backtracking
160162
search, and use the cost of the lowest-cost solution found so far as a lower bound on the cost of
161163
a least-cost solution to the problem, in order to discard partial solutions with costs larger than the
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
#Combination Sum Problem
2+
3+
Given a**set** of candidate numbers (`candidates`)**(without duplicates)** and
4+
a target number (`target`), find all unique combinations in`candidates` where
5+
the candidate numbers sums to`target`.
6+
7+
The**same** repeated number may be chosen from`candidates` unlimited number
8+
of times.
9+
10+
**Note:**
11+
12+
- All numbers (including`target`) will be positive integers.
13+
- The solution set must not contain duplicate combinations.
14+
15+
##Examples
16+
17+
```
18+
Input: candidates = [2,3,6,7], target = 7,
19+
20+
A solution set is:
21+
[
22+
[7],
23+
[2,2,3]
24+
]
25+
```
26+
27+
```
28+
Input: candidates = [2,3,5], target = 8,
29+
30+
A solution set is:
31+
[
32+
[2,2,2,2],
33+
[2,3,3],
34+
[3,5]
35+
]
36+
```
37+
38+
##Explanations
39+
40+
Since the problem is to get all the possible results, not the best or the
41+
number of result, thus we don’t need to consider DP (dynamic programming),
42+
backtracking approach using recursion is needed to handle it.
43+
44+
Here is an example of decision tree for the situation when`candidates = [2, 3]` and`target = 6`:
45+
46+
```
47+
0
48+
/ \
49+
+2 +3
50+
/ \ \
51+
+2 +3 +3
52+
/ \ / \ \
53+
+2 ✘ ✘ ✘ ✓
54+
/ \
55+
✓ ✘
56+
```
57+
58+
##References
59+
60+
-[LeetCode](https://leetcode.com/problems/combination-sum/description/)
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
importcombinationSumfrom'../combinationSum';
2+
3+
describe('combinationSum',()=>{
4+
it('should find all combinations with specific sum',()=>{
5+
expect(combinationSum([1],4)).toEqual([
6+
[1,1,1,1],
7+
]);
8+
9+
expect(combinationSum([2,3,6,7],7)).toEqual([
10+
[2,2,3],
11+
[7],
12+
]);
13+
14+
expect(combinationSum([2,3,5],8)).toEqual([
15+
[2,2,2,2],
16+
[2,3,3],
17+
[3,5],
18+
]);
19+
20+
expect(combinationSum([2,5],3)).toEqual([]);
21+
22+
expect(combinationSum([],3)).toEqual([]);
23+
});
24+
});
Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
/**
2+
*@param {number[]} candidates - candidate numbers we're picking from.
3+
*@param {number} remainingSum - remaining sum after adding candidates to currentCombination.
4+
*@param {number[][]} finalCombinations - resulting list of combinations.
5+
*@param {number[]} currentCombination - currently explored candidates.
6+
*@param {number} startFrom - index of the candidate to start further exploration from.
7+
*@return {number[][]}
8+
*/
9+
functioncombinationSumRecursive(
10+
candidates,
11+
remainingSum,
12+
finalCombinations=[],
13+
currentCombination=[],
14+
startFrom=0,
15+
){
16+
if(remainingSum<0){
17+
// By adding another candidate we've gone below zero.
18+
// This would mean that last candidate was not acceptable.
19+
returnfinalCombinations;
20+
}
21+
22+
if(remainingSum===0){
23+
// In case if after adding the previous candidate out remaining sum
24+
// became zero we need to same current combination since it is one
25+
// of the answer we're looking for.
26+
finalCombinations.push(currentCombination.slice());
27+
28+
returnfinalCombinations;
29+
}
30+
31+
// In case if we haven't reached zero yet let's continue to add all
32+
// possible candidates that are left.
33+
for(letcandidateIndex=startFrom;candidateIndex<candidates.length;candidateIndex+=1){
34+
constcurrentCandidate=candidates[candidateIndex];
35+
36+
// Let's try to add another candidate.
37+
currentCombination.push(currentCandidate);
38+
39+
// Explore further option with current candidate being added.
40+
combinationSumRecursive(
41+
candidates,
42+
remainingSum-currentCandidate,
43+
finalCombinations,
44+
currentCombination,
45+
candidateIndex,
46+
);
47+
48+
// BACKTRACKING.
49+
// Let's get back, exclude current candidate and try another ones later.
50+
currentCombination.pop();
51+
}
52+
53+
returnfinalCombinations;
54+
}
55+
56+
/**
57+
* Backtracking algorithm of finding all possible combination for specific sum.
58+
*
59+
*@param {number[]} candidates
60+
*@param {number} target
61+
*@return {number[][]}
62+
*/
63+
exportdefaultfunctioncombinationSum(candidates,target){
64+
returncombinationSumRecursive(candidates,target);
65+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp