V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Combination Sum

Choose reusable candidates in nondecreasing order, prune sums above the target, and avoid duplicate combinations.

Core idea

Sort candidates and keep a start index so choices never decrease. Reusing the same index permits repeated values, while a negative remaining target prunes the branch.

Read the visualization

Each decision edge subtracts one candidate from the remainder. Green leaves reach zero, pruned nodes exceed the target, and backtracking restores the previous remainder.

select 1select 2select 3select 4select 3select 4select 4select 2select 3select 4select 3select 4select 4{1,2,3}{1,2,4}{1,3,4}{1,4}{2,3}{2,4}{3,4}

Begin with an empty combination and the full remaining target.

1function combinationSum(cands: number[], target: number): number[][] {
2 const res: number[][] = [];
3 const cur: number[] = [];
4 const backtrack = (start: number, sum: number): void => {
5 if (sum === target) {
6 res.push([...cur]);
7 return;
8 }
9 for (let i = start; i < cands.length; i++) {
10 if (sum + cands[i] > target) continue; // prune: prune up prune target
11 cur.push(cands[i]);
12 backtrack(i + 1, sum + cands[i]);
13 cur.pop(); // backtrack( backtrack)
14 }
15 };
16 backtrack(0, 0);
17 return res;
18}
candidate1 2 3 4
target5
current combination∅
current sum0
searched to0
1 / 24

Complexity and tradeoffs

Time: Exponential in target depth. Space: O(target/min candidate). Output size dominates, while sorted candidates permit early pruning and canonical ordering.

Invariant: Every path is nondecreasing, so each mathematical combination has only one search-tree representation.

Where it fits

This pattern handles target sums, repeatable parts, and bounded construction. Changing the next start index switches between reusable and single-use candidates.