Generate All Combinations Sum K in DSA C#

Mental Model

Find all groups of numbers from a list that add up exactly to a target number 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 specific target. You try picking one bead, then another, and so on, backtracking if the total weight goes over the target.

Candidates: [2, 3, 6, 7]
Target: 7
Start -> [] (empty combination)
Try 2 -> [2]
Try 2 again -> [2 -> 2]
Try 3 -> [2 -> 2 -> 3]
Backtrack when sum > 7

Dry Run Walkthrough

Input: candidates: [2, 3, 6, 7], target: 7

Goal: Find all combinations of candidates that sum to 7

Step 1: Start with empty combination [] and sum 0

[] sum=0

Why: We begin with no numbers chosen and sum zero

Step 2: Add 2 to combination: [2], sum=2

[2] sum=2

Why: Try first candidate to explore possible sums

Step 3: Add 2 again: [2 -> 2], sum=4

[2 -> 2] sum=4

Why: We can reuse candidates, so try 2 again

Step 4: Add 3: [2 -> 2 -> 3], sum=7 (target reached)

[2 -> 2 -> 3] sum=7

Why: Sum matches target, record this combination

Step 5: Backtrack: remove last 3, try next candidate 6

[2 -> 2] sum=4

Why: 3 added sum to target, now try other options after backtracking

Step 6: Add 6: [2 -> 2 -> 6], sum=10 (exceeds target), backtrack

[2 -> 2] sum=4

Why: Sum exceeded target, discard this path

Step 7: Backtrack twice to [2], try 3: [2 -> 3], sum=5

[2 -> 3] sum=5

Why: Try next candidate after backtracking

Step 8: Add 3 again: [2 -> 3 -> 3], sum=8 (exceeds target), backtrack

[2 -> 3] sum=5

Why: Sum exceeded target, discard path

Step 9: Backtrack to [], try 3: [3], sum=3

[3] sum=3

Why: Try starting with next candidate

Step 10: Add 3 again: [3 -> 3], sum=6

[3 -> 3] sum=6

Why: Try reusing candidate 3

Step 11: Add 3 again: [3 -> 3 -> 3], sum=9 (exceeds target), backtrack

[3 -> 3] sum=6

Why: Sum exceeded target, discard path

Step 12: Backtrack to [], try 6: [6], sum=6

[6] sum=6

Why: Try next candidate

Step 13: Add 7: [7], sum=7 (target reached)

[7] sum=7

Why: Single candidate equals target, record combination

Result:

[2 -> 2 -> 3] sum=7
[7] sum=7
All combinations found

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class CombinationSum {
    public IList<IList<int>> CombinationSumK(int[] candidates, int target) {
        var result = new List<IList<int>>();
        Array.Sort(candidates); // sort to help pruning
        Backtrack(candidates, target, 0, new List<int>(), result);
        return result;
    }

    private void Backtrack(int[] candidates, int target, int start, List<int> current, List<IList<int>> result) {
        if (target == 0) {
            result.Add(new List<int>(current)); // found valid combination
            return;
        }
        for (int i = start; i < candidates.Length; i++) {
            if (candidates[i] > target) break; // no need to continue if candidate too big
            current.Add(candidates[i]); // choose candidate
            Backtrack(candidates, target - candidates[i], i, current, result); // explore further with updated target
            current.RemoveAt(current.Count - 1); // backtrack
        }
    }

    static void Main() {
        var cs = new CombinationSum();
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        var combos = cs.CombinationSumK(candidates, target);
        foreach (var combo in combos) {
            Console.WriteLine(string.Join(" -> ", combo) + " -> null");
        }
    }
}

Array.Sort(candidates); // sort to help pruning

sort candidates to stop early when sum exceeds target

if (target == 0) { result.Add(new List<int>(current)); return; }

record combination when target sum reached

if (candidates[i] > target) break;

stop exploring if candidate is too large to reach target

current.Add(candidates[i]);

choose candidate to add to current combination

Backtrack(candidates, target - candidates[i], i, current, result);

recurse with reduced target and same start to allow reuse

current.RemoveAt(current.Count - 1);

remove last candidate to backtrack and try next

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 up to target sum, plus output space for combinations

vs Alternative: Better than brute force checking all subsets because pruning stops exploring paths exceeding target early

Edge Cases

empty candidates array

returns empty list since no combinations possible

DSA C#

for (int i = start; i < candidates.Length; i++) {

target is zero

returns list with one empty combination

DSA C#

if (target == 0) { result.Add(new List<int>(current)); return; }

candidates contain duplicates

duplicates allowed, combinations may include repeated numbers

DSA C#

Backtrack(candidates, target - candidates[i], i, current, result);

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 and build combinations efficiently.

Common Mistakes

Mistake: Not backtracking by removing last added candidate after recursive call
Fix: Always remove last candidate after recursion to explore other paths

Mistake: Not sorting candidates and failing to prune early
Fix: Sort candidates and break loop when candidate exceeds remaining target

Summary

Finds all combinations of numbers that add up to a target sum.

Use when you need every possible group of numbers summing to a value, allowing repeats.

Try each number, explore deeper 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 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