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.

Practice

1. What does the problem "Generate All Combinations Sum K" ask you to find?

easy

A. The count of numbers equal to K

B. The largest number less than K

C. All unique combinations of numbers that add up to K

D. The smallest number greater than K

Solution

1. Step 1: Understand the problem goal

   The problem asks to find all unique sets of numbers whose sum equals K.

2. Step 2: Clarify uniqueness and sum condition

   Each combination must sum exactly to K without duplicates in the result.

3. Final Answer:

   All unique combinations of numbers that add up to K -> Option C

4. Quick Check:

   Combinations sum to K = All unique combinations of numbers that add up to K [OK]

Hint: Focus on combinations that sum exactly to K [OK]

Common Mistakes:

• Confusing sum with count
• Including duplicate combinations
• Looking for single numbers only

2. Which of the following TypeScript function signatures correctly represents a function to generate all combinations summing to K from an array of numbers?

easy

A. function generateCombinations(nums: number, target: number[]): number[]

B. function generateCombinations(nums: number[], target: number): number[][]

C. function generateCombinations(nums: string[], target: string): string[]

D. function generateCombinations(nums: number[], target: number): number[]

Solution

1. Step 1: Analyze parameter types

   The function should take an array of numbers and a target number.

2. Step 2: Analyze return type

   It should return an array of arrays of numbers representing combinations.

3. Final Answer:

   function generateCombinations(nums: number[], target: number): number[][] -> Option B

4. Quick Check:

   Input array and target number, output array of number arrays [OK]

Hint: Input array and target number, output array of arrays [OK]

Common Mistakes:

• Using wrong parameter types
• Returning flat array instead of array of arrays
• Mixing string and number types

3. What is the output of the following TypeScript code?

function combineSum(nums: number[], target: number): number[][] {
  const result: number[][] = [];
  function backtrack(start: number, path: number[], sum: number) {
    if (sum === target) {
      result.push([...path]);
      return;
    }
    if (sum > target) return;
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path, sum + nums[i]);
      path.pop();
    }
  }
  backtrack(0, [], 0);
  return result;
}

console.log(combineSum([1, 2, 3], 3));

medium

A. [[1, 2], [3]]

B. [[1, 3], [2]]

C. [[3], [2, 1]]

D. [[1, 2, 3]]

Solution

1. Step 1: Trace backtracking calls

   Starting from 0, combinations are built adding numbers without reuse: [1,2] sums to 3, [3] sums to 3.

2. Step 2: Confirm valid combinations

   Other combinations like [2] or [1,3] do not sum to 3 or are invalid due to index increment.

3. Final Answer:

   [[1, 2], [3]] -> Option A

4. Quick Check:

   Combinations summing to 3 = [[1, 2], [3]] [OK]

Hint: Check sums and index increments carefully [OK]

Common Mistakes:

• Including combinations with reused elements
• Ignoring sum > target condition
• Confusing order of elements

4. Identify the bug in this TypeScript function that aims to generate all combinations summing to K:

function findCombos(nums: number[], target: number): number[][] {
  const res: number[][] = [];
  function dfs(i: number, path: number[], total: number) {
    if (total === target) {
      res.push(path);
      return;
    }
    if (total > target || i === nums.length) return;
    dfs(i + 1, path, total);
    path.push(nums[i]);
    dfs(i + 1, path, total + nums[i]);
    path.pop();
  }
  dfs(0, [], 0);
  return res;
}

medium

A. The function does not return any result

B. The base case does not check for total > target

C. The recursion does not increment index i

D. The path array is pushed by reference causing incorrect results

Solution

1. Step 1: Check how path is stored

   The path array is pushed directly without copying, so later changes affect stored results.

2. Step 2: Understand impact on results

   Because path is referenced, all stored combinations end up empty or incorrect after backtracking.

3. Final Answer:

   The path array is pushed by reference causing incorrect results -> Option D

4. Quick Check:

   Push copy of path, not reference [OK]

Hint: Always push a copy of path, not the original [OK]

Common Mistakes:

• Pushing path without copying
• Not handling base cases properly
• Incorrect index increment

5. Given an array with duplicates, how can you modify the combination sum algorithm to generate all unique combinations summing to K without duplicates in the result?

nums = [1, 2, 2, 3], target = 4

hard

A. Sort the array and skip duplicates during recursion

B. Use a Set to store all combinations as strings

C. Allow duplicates and filter results after generation

D. Ignore duplicates and generate all combinations

Solution

1. Step 1: Sort the input array

   Sorting groups duplicates together, making it easier to skip them during recursion.

2. Step 2: Skip duplicates in recursion

   When iterating, skip elements equal to the previous to avoid duplicate combinations.

3. Final Answer:

   Sort the array and skip duplicates during recursion -> Option A

4. Quick Check:

   Sorting + skipping duplicates = unique combinations [OK]

Hint: Sort and skip duplicates while recursing [OK]

Common Mistakes:

• Not sorting before recursion
• Filtering duplicates after generation (inefficient)
• Ignoring duplicates causing repeated results