Generate All Combinations Sum K in DSA C - 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

↓

Save combination

↓

Backtrack: remove last number

↓

Try next candidate

↓

End when all candidates tried or sum > K

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

Execution Sample

DSA C

void backtrack(int start, int sum, int k, int* comb, int combSize) {
  if (sum == k) { /* print_comb(comb, combSize); */ return; }
  for (int i = start; i < n; i++) {
    if (sum + candidates[i] <= k) {
      comb[combSize] = candidates[i];
      backtrack(i, sum + candidates[i], k, comb, combSize + 1);
    }
  }
}

Recursively build combinations by adding candidates while sum does not exceed K, print when sum equals K.

Execution Table

Step	Operation	Current Combination	Sum	Action	Visual State
1	Start	[]	0	Begin with empty combination	[]
2	Add 1	[1]	1	Sum < K, recurse deeper	[1]
3	Add 1	[1,1]	2	Sum < K, recurse deeper	[1 -> 1]
4	Add 1	[1,1,1]	3	Sum == K, save combination	[1 -> 1 -> 1]
5	Backtrack	[1,1]	2	Remove last 1, try next candidate	[1 -> 1]
6	Add 2	[1,1,2]	4	Sum > K, skip	[1 -> 1]
7	Backtrack	[1]	1	Remove last 1, try next candidate	[1]
8	Add 2	[1,2]	3	Sum == K, save combination	[1 -> 2]
9	Backtrack	[1]	1	Remove last 2, try next candidate	[1]
10	Add 3	[1,3]	4	Sum > K, skip	[1]
11	Backtrack	[]	0	Remove last 1, try next candidate	[]
12	Add 2	[2]	2	Sum < K, recurse deeper	[2]
13	Add 2	[2,2]	4	Sum > K, skip	[2]
14	Add 3	[2,3]	5	Sum > K, skip	[2]
15	Backtrack	[]	0	Remove last 2, try next candidate	[]
16	Add 3	[3]	3	Sum == K, save combination	[3]
17	Backtrack	[]	0	All candidates tried, end	[]

💡 All candidates tried or sum exceeded K, recursion ends

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 8	After Step 12	After Step 16	Final
combination	[]	[1]	[1,1,1]	[1,2]	[2]	[3]	[]
sum	0	1	3	3	2	3	0
step	1	2	4	8	12	16	17

Key Moments - 3 Insights

Why do we backtrack after reaching sum == K?

Because after saving a valid combination (step 4), we remove the last number to try other possibilities (step 5), as shown in the execution_table.

Why do we skip adding a number when sum + candidate > K?

To avoid invalid combinations exceeding K, the code skips adding that candidate (step 6), preventing unnecessary recursion.

Why do we start the next recursion from the current index, not zero?

Starting from current index (not zero) avoids duplicates and allows repeated use of the same number, as seen in steps 2 and 3.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the current combination?

A [1,1,1]

B [1,2]

C [2,3]

D [3]

💡 Hint

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

At which step does the sum first equal K?

A Step 2

B Step 4

C Step 8

D Step 12

💡 Hint

Look at the 'Sum' and 'Action' columns in the execution_table to find when sum == K.

If we change K to 4, which step would change in the execution_table?

A Step 4 would no longer save combination

B Step 8 would save combination with sum 4

C Step 16 would save combination with sum 4

D Step 6 would add a new candidate

💡 Hint

Check which sums equal K in the execution_table and how changing K affects saving combinations.

Concept Snapshot

Generate All Combinations Sum K:
- Use backtracking to build combinations
- Add candidates while sum ≤ K
- Save combination when sum == K
- Backtrack to try other candidates
- Avoid duplicates by starting from current index
- Stop recursion when sum > K

Full Transcript

This concept shows how to generate all combinations of numbers that add up to a target sum K. We start with an empty list and add numbers one by one from the candidates. If the sum equals K, we save the combination. If the sum is less than K, we continue adding numbers recursively. If the sum exceeds K, we stop and backtrack to try other numbers. We avoid duplicates by always starting the next recursion from the current candidate index. The execution table traces each step, showing the current combination, sum, and actions taken. Key moments explain why backtracking is needed and why we skip candidates that exceed the sum. The visual quiz tests understanding of the combination states and recursion flow.