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.