Generate All Combinations Sum K in DSA C# - Execution Trace

Concept Flow - Generate All Combinations Sum K

Start with empty combination

↓

Pick next number from candidates

↓

Add number to combination

↓

Check sum of combination

↓

Save

↓

Try next number or backtrack

↓

End

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

Execution Sample

DSA C#

void Backtrack(int start, int k, List<int> comb, List<List<int>> res, int[] nums) {
  if (k == 0) {
    res.Add(new List<int>(comb));
    return;
  }
  for (int i = start; i < nums.Length; i++) {
    if (nums[i] > k) break;
    comb.Add(nums[i]);
    Backtrack(i + 1, k - nums[i], comb, res, nums);
    comb.RemoveAt(comb.Count - 1);
  }
}

This code finds all combinations of numbers that sum to k by exploring candidates recursively and backtracking.

Execution Table

Step	Operation	Current Combination	Remaining Sum (k)	Action	Visual State
1	Start Backtrack(0, 7, [], [], [2,3,6,7])	[]	7	Begin search	[]
2	Pick nums[0] = 2	[]	7	Add 2	[2]
3	Backtrack(1, 5, [2], [], [2,3,6,7])	[2]	5	Recurse	[2]
4	Pick nums[1] = 3	[2]	5	Add 3	[2,3]
5	Backtrack(2, 2, [2,3], [], [2,3,6,7])	[2,3]	2	Recurse	[2,3]
6	Pick nums[2] = 6	[2,3]	2	6 > 2, break loop	[2,3]
7	Backtrack returns, remove 3	[2,3]	5	Backtrack	[2]
8	Pick nums[2] = 6	[2]	5	6 > 5, break loop	[2]
9	Backtrack returns, remove 2	[2]	7	Backtrack	[]
10	Pick nums[1] = 3	[]	7	Add 3	[3]
11	Backtrack(2, 4, [3], [], [2,3,6,7])	[3]	4	Recurse	[3]
12	Pick nums[2] = 6	[3]	4	6 > 4, break loop	[3]
13	Backtrack returns, remove 3	[3]	7	Backtrack	[]
14	Pick nums[2] = 6	[]	7	Add 6	[6]
15	Backtrack(3, 1, [6], [], [2,3,6,7])	[6]	1	Recurse	[6]
16	Pick nums[3] = 7	[6]	1	7 > 1, break loop	[6]
17	Backtrack returns, remove 6	[6]	7	Backtrack	[]
18	Pick nums[3] = 7	[]	7	Add 7	[7]
19	Backtrack(4, 0, [7], [], [2,3,6,7])	[7]	0	Sum == 0, save combination	[7]
20	Backtrack returns, remove 7	[7]	7	Backtrack	[]
21	End of candidates, search complete	[]	7	Done	[]

💡 All candidates tried or sum exceeded, recursion ends.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 5	After Step 7	After Step 10	After Step 14	After Step 18	Final
combination	[]	[2]	[2,3]	[2,3]	[2]	[3]	[6]	[7]	[]
remaining sum (k)	7	5	2	2	5	4	1	0	7
result list	[]	[]	[]	[]	[]	[]	[]	[[7]]	[[7]]

Key Moments - 3 Insights

Why do we remove the last number after each recursive call?

Because after exploring combinations including that number, we must backtrack to try other numbers. See steps 7, 9, 13, 17, and 20 where removal happens to explore new paths.

Why do we stop exploring when the candidate number is greater than the remaining sum?

Because adding a number larger than the remaining sum would exceed the target. This is shown in steps 6, 8, 12, 16 where the loop breaks early to avoid unnecessary work.

When do we save a combination to the result list?

When the remaining sum reaches zero, meaning the current combination sums exactly to K. This happens at step 19 where [7] is saved.

Visual Quiz - 3 Questions

Look at the execution table at step 5, what is the current combination and remaining sum?

A [3], 4

B [2,3], 2

C [2], 5

D [6], 1

💡 Hint

Check the 'Current Combination' and 'Remaining Sum (k)' columns at step 5.

At which step does the algorithm save a valid combination?

A Step 19

B Step 10

C Step 7

D Step 14

💡 Hint

Look for the step where 'Sum == 0, save combination' appears in the 'Action' column.

If the candidate 6 was removed from the input, how would the execution table change?

A Algorithm would fail to find any combination

B No change, 6 is never used

C Steps involving 6 would be skipped, fewer backtracks

D The combination [7] would not be found

💡 Hint

Check steps 6, 8, 14, 15, 16, 17 where 6 is involved.

Concept Snapshot

Generate All Combinations Sum K:
- Use backtracking to build combinations.
- Add numbers if sum <= K.
- Save combination if sum == K.
- Remove last number to backtrack.
- Stop exploring if number > remaining sum.
- Explore candidates in order to avoid duplicates.

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 pick numbers one by one from a sorted list. If adding a number keeps the sum less than or equal to K, we add it and recurse. If the sum equals K, we save the combination. If the sum exceeds K or no more candidates remain, we backtrack by removing the last added number and try other candidates. The execution table tracks each step, showing the current combination, remaining sum, and actions like adding, backtracking, or saving. Key moments clarify why we remove numbers after recursion, why we stop early when numbers exceed the remaining sum, and when we save valid combinations. The quiz tests understanding of the combination state at specific steps and the effect of removing candidates.

Practice

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

easy

A. The largest number less than K

B. The sum of all numbers from 1 to K

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

D. The product of all numbers that divide K

Solution

1. Step 1: Understand the problem goal

   The problem asks to find all unique sets of numbers that add exactly to K.

2. Step 2: Identify the correct description

   All unique combinations of numbers that add up to K correctly describes finding all unique combinations summing to K.

3. Final Answer:

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

4. Quick Check:

   Combinations sum K = all sets adding to K [OK]

Hint: Look for options describing sets adding exactly to K [OK]

Common Mistakes:

• Confusing sum with product
• Thinking about single numbers instead of combinations
• Choosing options about divisors or ranges

2. Which of the following is the correct C# syntax to start a recursive method named FindCombinations that takes a list of integers and a target sum?

easy

A. void FindCombinations(List nums, int target) { }

B. void FindCombinations(List<int> nums, int target) { }

C. void FindCombinations(int nums[], int target) { }

D. void FindCombinations(List<int> nums; int target) { }

Solution

1. Step 1: Check parameter types and syntax

   In C#, a list of integers is declared as List<int>. The method parameters must be separated by commas.

2. Step 2: Identify correct syntax

   void FindCombinations(List<int> nums, int target) { } uses List<int> and comma-separated parameters correctly. Others have syntax errors or wrong types.

3. Final Answer:

   void FindCombinations(List<int> nums, int target) { } -> Option B

4. Quick Check:

   Correct C# method syntax = void FindCombinations(List<int> nums, int target) { } [OK]

Hint: Remember C# uses List<int> and commas between parameters [OK]

Common Mistakes:

• Using array syntax int nums[] in method parameters
• Missing commas between parameters
• Using untyped List without <int>

3. What is the output of the following C# code snippet that generates all combinations of numbers from 1 to 3 that sum to 3?

void Generate(int start, int target, List<int> current, List result) {
  if (target == 0) {
    result.Add(new List<int>(current));
    return;
  }
  for (int i = start; i <= 3; i++) {
    if (i <= target) {
      current.Add(i);
      Generate(i + 1, target - i, current, result);
      current.RemoveAt(current.Count - 1);
    }
  }
}

var result = new List();
Generate(1, 3, new List<int>(), result);
foreach(var combo in result) {
  Console.WriteLine(string.Join(",", combo));
}

medium

A. 3
2,1

B. 1,1,1
3

C. 1,2
2,1
3

D. 1,2
3

Solution

1. Step 1: Trace recursive calls and combinations

   The code tries numbers from start to 3, adding to current if <= target. It avoids repeats by increasing start each call.

2. Step 2: Identify valid combinations summing to 3

   Possible combinations are [1,2] and [3]. The code prints these two lines: "1,2" and "3".

3. Final Answer:

   1,2 3 -> Option D

4. Quick Check:

   Unique combos summing 3 = 1,2 and 3 [OK]

Hint: Check recursion start index to avoid duplicates [OK]

Common Mistakes:

• Expecting repeated numbers like 1,1,1
• Confusing order of output lines
• Including reversed duplicates like 2,1

4. The following code is intended to generate all combinations of numbers from 1 to 4 that sum to 5. What is the main error causing it to miss some combinations?

void Generate(int start, int target, List<int> current, List result) {
  if (target == 0) {
    result.Add(new List<int>(current));
    return;
  }
  for (int i = start; i < 4; i++) {
    if (i <= target) {
      current.Add(i);
      Generate(i + 1, target - i, current, result);
      current.RemoveAt(current.Count - 1);
    }
  }
}

medium

A. The loop condition should be <= 4, not < 4

B. The recursive call should use i, not i + 1

C. The target check should be target < i, not i <= target

D. The current list should not be copied when adding to result

Solution

1. Step 1: Analyze the for loop range

   The loop runs from start to i < 4, so it stops at i=3, missing i=4.

2. Step 2: Identify impact on combinations

   Because 4 is excluded, combinations including 4 are missed. Changing to i <= 4 fixes this.

3. Final Answer:

   The loop condition should be <= 4, not < 4 -> Option A

4. Quick Check:

   Loop range excludes 4, missing combos [OK]

Hint: Check loop boundaries carefully for inclusive ranges [OK]

Common Mistakes:

• Using wrong loop end condition
• Changing recursion start incorrectly
• Not copying list before adding to result

5. You want to generate all combinations of numbers from 1 to 7 that sum to 7, but each number can be used multiple times. Which change to the recursive call in this C# code will allow repeated numbers?

void Generate(int start, int target, List<int> current, List result) {
  if (target == 0) {
    result.Add(new List<int>(current));
    return;
  }
  for (int i = start; i <= 7; i++) {
    if (i <= target) {
      current.Add(i);
      Generate(??? , target - i, current, result);
      current.RemoveAt(current.Count - 1);
    }
  }
}

hard

A. Use i to allow repeats

B. Use start to allow repeats

C. Use i + 1 to avoid repeats

D. Use 1 to restart from beginning

Solution

1. Step 1: Understand how recursion controls repeats

   Using i + 1 moves start forward, preventing repeats. Using i keeps start same, allowing repeats.

2. Step 2: Choose correct recursive call argument

   To allow repeated numbers, pass i as start in recursive call.

3. Final Answer:

   Use i to allow repeats -> Option A

4. Quick Check:

   Passing i keeps current number available [OK]

Hint: Pass current index to allow repeats, increment to avoid [OK]

Common Mistakes:

• Using i + 1 disables repeats
• Using start (unchanged) may cause infinite loops
• Restarting from 1 causes duplicates and inefficiency