Combination Sum
Find all unique combinations in array where chosen numbers sum to target. Numbers can be reused. Classic backtracking problem with pruning optimization.
Visualization
Interactive visualization for Combination Sum
Combination Sum
• Backtracking with reusable elements
• Pruning when sum > target
• Classic subset generation problem
Interactive visualization with step-by-step execution
Implementation
1function combinationSum(candidates: number[], target: number): number[][] {
2 const result: number[][] = [];
3 const current: number[] = [];
4 candidates.sort((a, b) => a - b);
5
6 function backtrack(start: number, remaining: number): void {
7 if (remaining === 0) {
8 result.push([...current]);
9 return;
10 }
11
12 for (let i = start; i < candidates.length; i++) {
13 if (candidates[i] > remaining) break; // Pruning
14
15 current.push(candidates[i]);
16 backtrack(i, remaining - candidates[i]); // Can reuse same element
17 current.pop();
18 }
19 }
20
21 backtrack(0, target);
22 return result;
23}
24
25// Combination Sum II (no duplicates, each number used once)
26function combinationSum2(candidates: number[], target: number): number[][] {
27 const result: number[][] = [];
28 const current: number[] = [];
29 candidates.sort((a, b) => a - b);
30
31 function backtrack(start: number, remaining: number): void {
32 if (remaining === 0) {
33 result.push([...current]);
34 return;
35 }
36
37 for (let i = start; i < candidates.length; i++) {
38 if (i > start && candidates[i] === candidates[i - 1]) continue; // Skip duplicates
39 if (candidates[i] > remaining) break;
40
41 current.push(candidates[i]);
42 backtrack(i + 1, remaining - candidates[i]); // Move to next
43 current.pop();
44 }
45 }
46
47 backtrack(0, target);
48 return result;
49}Deep Dive
Theoretical Foundation
Explore all combinations by trying each candidate, recursing with reduced target. Backtrack when target becomes negative or zero. Sort array and prune when current candidate exceeds remaining target.
Complexity
Time
O(2^t)
O(2^t)
O(2^t)
Space
O(t) recursion depth
Applications
Industry Use
Coin change problem variations
Subset sum and partition problems
Resource allocation with constraints
Knapsack problem variants
Budget planning and optimization
Recipe ingredient combinations
Investment portfolio selection
Use Cases
Related Algorithms
N-Queens Problem
The N-Queens Problem asks: place N chess queens on an N×N chessboard so that no two queens threaten each other. This means no two queens can be on the same row, column, or diagonal. It's a classic constraint satisfaction problem that demonstrates backtracking, pruning, and systematic exploration of solution spaces. The problem has applications in parallel processing, resource allocation, and algorithm design education.
Sudoku Solver
Sudoku Solver uses backtracking to fill a 9×9 grid with digits 1-9, ensuring each row, column, and 3×3 box contains all digits exactly once. This classic constraint satisfaction problem demonstrates systematic exploration with constraint checking. The algorithm fills empty cells one by one, backtracking when constraints are violated, making it a perfect example of pruning in search algorithms.
Generate Valid Parentheses
Generate all combinations of n pairs of well-formed parentheses. Uses backtracking with constraint that closing parentheses never exceed opening ones.
Word Search in Grid
Given 2D board and word, find if word exists in grid. Word must be constructed from letters of sequentially adjacent cells (horizontally or vertically). Uses backtracking with visited tracking.