Generate All Combinations Sum K in DSA Typescript - Execution Trace

Concept Flow - Generate All Combinations Sum K

Start with empty combination

↓

Choose next number from candidates

↓

Add number to current combination

↓

Check sum of combination

↓

Continue

↓

Backtrack: remove last number

↓

Try next number

↓

Repeat until all combinations tried

Start with an empty list, pick numbers one by one, add them if sum is less than K, save if sum equals K, backtrack to try other numbers.

Execution Sample

DSA Typescript

function combineSumK(candidates: number[], k: number): number[][] {
  const result: number[][] = [];
  function backtrack(start: number, combo: number[], sum: number) {
    if (sum === k) result.push([...combo]);
    else if (sum < k) {
      for (let i = start; i < candidates.length; i++) {
        combo.push(candidates[i]);
        backtrack(i + 1, combo, sum + candidates[i]);
        combo.pop();
      }
    }
  }
  backtrack(0, [], 0);
  return result;
}

Find all unique combinations of numbers that add up to k by exploring candidates recursively.

Execution Table

Step	Operation	Current Combination	Sum	Action	Visual State
1	Start backtrack(0, [], 0)	[]	0	Check sum=0 < k=5	[]
2	Add candidates[0]=1	[1]	1	Sum 1 < 5, recurse	[1]
3	Add candidates[1]=2	[1,2]	3	Sum 3 < 5, recurse	[1 -> 2]
4	Add candidates[2]=3	[1,2,3]	6	Sum 6 > 5, backtrack	[1 -> 2 -> 3]
5	Remove 3	[1,2]	3	Backtrack	[1 -> 2]
6	Add candidates[3]=4	[1,2,4]	7	Sum 7 > 5, backtrack	[1 -> 2 -> 4]
7	Remove 4	[1,2]	3	Backtrack	[1 -> 2]
8	Remove 2	[1]	1	Backtrack	[1]
9	Add candidates[2]=3	[1,3]	4	Sum 4 < 5, recurse	[1 -> 3]
10	Add candidates[3]=4	[1,3,4]	8	Sum 8 > 5, backtrack	[1 -> 3 -> 4]
11	Remove 4	[1,3]	4	Backtrack	[1 -> 3]
12	Remove 3	[1]	1	Backtrack	[1]
13	Add candidates[3]=4	[1,4]	5	Sum 5 == 5, save combo	[1 -> 4]
14	Remove 4	[1]	1	Backtrack	[1]
15	Remove 1	[]	0	Backtrack	[]
16	Add candidates[1]=2	[2]	2	Sum 2 < 5, recurse	[2]
17	Add candidates[2]=3	[2,3]	5	Sum 5 == 5, save combo	[2 -> 3]
18	Remove 3	[2]	2	Backtrack	[2]
19	Add candidates[3]=4	[2,4]	6	Sum 6 > 5, backtrack	[2 -> 4]
20	Remove 4	[2]	2	Backtrack	[2]
21	Remove 2	[]	0	Backtrack	[]
22	Add candidates[2]=3	[3]	3	Sum 3 < 5, recurse	[3]
23	Add candidates[3]=4	[3,4]	7	Sum 7 > 5, backtrack	[3 -> 4]
24	Remove 4	[3]	3	Backtrack	[3]
25	Remove 3	[]	0	Backtrack	[]
26	Add candidates[3]=4	[4]	4	Sum 4 < 5, recurse	[4]
27	No more candidates to add	[4]	4	Backtrack	[4]
28	Remove 4	[]	0	Backtrack	[]
29	End recursion	[]	0	All combinations tried	[]

💡 All candidates explored, recursion ends

Variable Tracker

Variable	Start	After Step 2	After Step 9	After Step 13	After Step 17	After Step 22	After Step 26	Final
combo	[]	[1]	[1,3]	[1,4]	[2,3]	[3]	[4]	[]
sum	0	1	4	5	5	3	4	0
result	[]	[]	[]	[[1,4]]	[[1,4],[2,3]]	[[1,4],[2,3]]	[[1,4],[2,3]]	[[1,4],[2,3]]

Key Moments - 3 Insights

Why do we backtrack (remove last number) after recursion?

Because after exploring combinations including that number, we must remove it to try other numbers (see steps 4, 7, 11). This ensures all combinations are explored without duplicates.

Why do we stop recursion when sum exceeds k?

Because adding more numbers will only increase sum, so no valid combination can be formed beyond that point (see steps 4, 6, 10). This saves time by pruning.

How do we know when to save a combination?

When the sum equals k exactly, we copy and save the current combination (see steps 13 and 17). This is the base case for success.

Visual Quiz - 3 Questions

Look at the execution table at step 13, what is the current combination?

A [1,3]

B [1,4]

C [2,3]

D [3,4]

💡 Hint

Check the 'Current Combination' column at step 13 in the execution_table.

At which step does the sum first exceed k=5?

A Step 4

B Step 13

C Step 17

D Step 22

💡 Hint

Look for the first 'Sum' value greater than 5 in the execution_table.

If we change candidates to include 5, how would the result change?

A Only combinations with 1 and 2 would change

B No change, 5 is ignored

C More combinations including 5 would be found

D The algorithm would stop early

💡 Hint

Adding 5 as a candidate allows new combinations summing to 5, check how candidates affect results in variable_tracker.

Concept Snapshot

Generate All Combinations Sum K:
- Use backtracking to explore candidates
- Add numbers if sum < K
- Save combination if sum == K
- Remove last number to backtrack
- Repeat until all combos tried

Full Transcript

This visualization shows how to generate all combinations of numbers that sum to a target K using backtracking. We start with an empty combination and try adding each candidate number. If the sum is less than K, we continue adding more numbers recursively. If the sum equals K, we save the current combination. If the sum exceeds K, we backtrack by removing the last number and try other candidates. This process repeats until all possible combinations are explored. The execution table tracks each step, the current combination, sum, and actions taken. The variable tracker shows how the combination and sum change over time. Key moments clarify why backtracking is needed, when to save combinations, and why pruning occurs. The quiz tests understanding of these steps and outcomes.

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