Generate All Combinations Sum K in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of combinations summing to K

What is the output of the following C# code that generates all combinations of numbers from 1 to 4 that sum to 5?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        var results = new List<List<int>>();
        GenerateCombinations(1, 4, 5, new List<int>(), results);
        foreach (var combo in results) {
            Console.WriteLine(string.Join(", ", combo));
        }
    }

    static void GenerateCombinations(int start, int end, int target, List<int> current, List<List<int>> results) {
        if (target == 0) {
            results.Add(new List<int>(current));
            return;
        }
        for (int i = start; i <= end; i++) {
            if (i > target) break;
            current.Add(i);
            GenerateCombinations(i + 1, end, target - i, current, results);
            current.RemoveAt(current.Count - 1);
        }
    }

A

1, 4
2, 3
1, 2, 2

B

1, 4
2, 3

C

1, 4
2, 3
1, 1, 3

D

1, 4
2, 3
3, 2

💡 Hint

Focus on combinations of unique numbers that sum to 5 without repetition.

The code generates combinations of unique numbers from 1 to 4 that sum to 5. The valid combinations are [1,4] and [2,3]. It does not include repeated numbers like [1,2,2] or [1,1,3].

🧠 Conceptual

intermediate

Understanding the role of 'start' parameter

In the recursive function to generate all combinations summing to K, what is the purpose of the 'start' parameter?

A To track the current sum of the combination

B To limit the maximum number allowed in combinations

C To ensure numbers are chosen in ascending order and avoid duplicates

D To reset the combination list after each recursion

💡 Hint

Think about how duplicates are avoided in combinations.

The 'start' parameter ensures that each recursive call only considers numbers greater than the previous chosen number, maintaining ascending order and preventing duplicate combinations.

🔧 Debug

advanced

Identify the error in combination generation

What error will occur if the line 'current.RemoveAt(current.Count - 1);' is removed from the recursive function?

DSA C#

static void GenerateCombinations(int start, int end, int target, List<int> current, List<List<int>> results) {
    if (target == 0) {
        results.Add(new List<int>(current));
        return;
    }
    for (int i = start; i <= end; i++) {
        if (i > target) break;
        current.Add(i);
        GenerateCombinations(i + 1, end, target - i, current, results);
        // current.RemoveAt(current.Count - 1); // This line is removed
    }
}

A The program will run infinitely due to no backtracking

B No error, the output remains correct

C A runtime error will occur due to index out of range

D The combinations list will contain incorrect combinations with extra numbers

💡 Hint

Consider what happens to the 'current' list after recursive calls.

Without removing the last added number after recursion, the 'current' list keeps growing and does not backtrack properly, causing incorrect combinations to be recorded.

📝 Syntax

advanced

Identify the syntax error in combination code

Which option contains a syntax error in the following combination generation code snippet?

DSA C#

for (int i = start; i <= end; i++) {
    if (i > target) break
    current.Add(i);
    GenerateCombinations(i + 1, end, target - i, current, results);
    current.RemoveAt(current.Count - 1);
}

A Missing semicolon after 'break' statement

B Incorrect parameter order in recursive call

C Wrong loop variable declaration

D Incorrect method call syntax for 'Add' method

💡 Hint

Check each line carefully for punctuation.

The 'break' statement is missing a semicolon at the end, causing a syntax error.

🚀 Application

expert

Number of combinations for sum K

Given numbers from 1 to 7, how many unique combinations of numbers sum exactly to 10? The combinations must use each number at most once and order does not matter.

A 7

B 8

C 10

D 11

💡 Hint

Try to list or count all combinations manually or use a recursive approach.

The unique combinations of numbers from 1 to 7 that sum to 10 are: [1,2,3,4], [1,2,7], [1,3,6], [1,4,5], [2,3,5], [3,7], [4,6]. Correct count is 7.

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