Generate All Combinations Sum K in DSA Typescript

Mental Model

Find all groups of numbers from a list that add up exactly to a target sum by trying each number and exploring further choices.

Analogy: Imagine you have a box of different colored beads and want to pick some beads so their total weight equals a target weight. You try picking one bead, then try adding others until you reach the target or go over.

Candidates: [2, 3, 6, 7]
Target sum: 7

Start -> [] (empty combination)
Try 2 -> [2]
Try 3 -> [3]
Try 6 -> [6]
Try 7 -> [7]

Dry Run Walkthrough

Input: candidates: [2, 3, 6, 7], target sum: 7

Goal: Find all combinations of numbers from candidates that sum to 7

Step 1: Start with empty combination [] and target 7

[] (target=7)

Why: We begin with no numbers chosen and full target to reach

Step 2: Pick 2, combination becomes [2], reduce target to 5

[2] (target=5)

Why: Try including 2 and see if we can reach target by adding more

Step 3: Pick 2 again (allowed), combination [2,2], target 3

[2, 2] (target=3)

Why: We can reuse numbers, so try 2 again to get closer to target

Step 4: Pick 3, combination [2, 2, 3], target 0

[2, 2, 3] (target=0)

Why: Sum matches target, so this is a valid combination

Step 5: Backtrack: remove last 3, try next candidate 6 at [2, 2]

[2, 2] (target=3)

Why: 3 was last candidate, try next to find other combos

Step 6: 6 is too big for target 3, backtrack to [2]

[2] (target=5)

Why: 6 exceeds target, so discard and backtrack

Step 7: Try 3 at [2], combination [2, 3], target 2

[2, 3] (target=2)

Why: Try next candidate to reach target

Step 8: Try 3 again at [2,3], combination [2,3,3], target -1 (invalid)

[2, 3, 3] (target=-1)

Why: Target negative means invalid path, backtrack

Step 9: Backtrack to [] and try 3, combination [3], target 4

[3] (target=4)

Why: Try starting with 3 to find other combos

Step 10: Try 3 again, combination [3, 3], target 1

[3, 3] (target=1)

Why: Try adding 3 again to get closer

Step 11: Try 6 at [3,3], too big for target 1, backtrack

[3, 3] (target=1)

Why: 6 exceeds target, discard

Step 12: Try 7 at [3,3], too big, backtrack to []

[] (target=7)

Why: Try next candidates from start

Step 13: Try 6, combination [6], target 1

[6] (target=1)

Why: Try 6 to see if we can reach target

Step 14: Try 7, combination [7], target 0 (valid)

[7] (target=0)

Why: 7 alone matches target, valid combination

Result:

[2, 2, 3] -> [7] -> null

Annotated Code

DSA Typescript

class CombinationSum {
  private results: number[][] = [];

  public findCombinations(candidates: number[], target: number): number[][] {
    this.results = [];
    candidates.sort((a, b) => a - b); // sort to help pruning
    this.backtrack(candidates, target, 0, []);
    return this.results;
  }

  private backtrack(candidates: number[], target: number, start: number, path: number[]): void {
    if (target === 0) {
      this.results.push([...path]); // found valid combination
      return;
    }
    if (target < 0) {
      return; // invalid path
    }

    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > target) {
        break; // no need to continue if candidate exceeds target
      }
      path.push(candidates[i]); // choose candidate
      this.backtrack(candidates, target - candidates[i], i, path); // explore further with updated target
      path.pop(); // backtrack
    }
  }
}

// Driver code
const combSum = new CombinationSum();
const candidates = [2, 3, 6, 7];
const target = 7;
const result = combSum.findCombinations(candidates, target);
for (const combo of result) {
  console.log(combo.join(' -> ') + ' -> null');
}

candidates.sort((a, b) => a - b);

sort candidates to enable early stopping when candidate > target

if (target === 0) { this.results.push([...path]); return; }

when target is zero, record current combination as valid

if (target < 0) { return; }

stop exploring paths that exceed target

for (let i = start; i < candidates.length; i++) {

iterate candidates from current start index to avoid duplicates

if (candidates[i] > target) { break; }

prune search when candidate is too large

path.push(candidates[i]);

choose candidate and add to current path

this.backtrack(candidates, target - candidates[i], i, path);

recurse with reduced target and same start to allow reuse

path.pop();

backtrack by removing last candidate to try others

Output

2 -> 2 -> 3 -> null

7 -> null

Complexity Analysis

Time: O(2^n) because each candidate can be chosen or not, leading to exponential combinations

Space: O(k) where k is the depth of recursion (max length of combination), plus output space

vs Alternative: Compared to brute force checking all subsets, pruning by sorting and early stopping reduces unnecessary paths

Edge Cases

empty candidates array

returns empty list since no combinations possible

DSA Typescript

for (let i = start; i < candidates.length; i++) {

target is zero

returns list with empty combination as valid

DSA Typescript

if (target === 0) { this.results.push([...path]); return; }

candidates with duplicates

duplicates allowed and can be reused multiple times

DSA Typescript

this.backtrack(candidates, target - candidates[i], i, path);

When to Use This Pattern

When asked to find all combinations that sum to a target with repeated use allowed, use backtracking with pruning to explore choices efficiently.

Common Mistakes

Mistake: Not sorting candidates and missing pruning opportunities
Fix: Sort candidates first and break loop when candidate > target to reduce search space

Mistake: Advancing start index incorrectly, causing missing valid combinations
Fix: Pass current index (i) in recursive call to allow reuse of same candidate

Mistake: Not backtracking (not removing last candidate) after recursion
Fix: Always pop last candidate after recursive call to restore state

Summary

Finds all groups of numbers from a list that add up exactly to a target sum.

Use when you need every possible combination that sums to a target, allowing repeated numbers.

Try each candidate, explore further with reduced target, and backtrack to try others.