Generate All Subsets Powerset in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

🧠 Conceptual

easy

Powerset Size

How many subsets does a set of n elements have, including the empty set?

A n!

B 2^n

C n²

D n × (n+1) / 2

💡 Hint

Each element has exactly two choices: included or excluded. Apply the multiplication rule.

For each of the n elements, there are exactly 2 choices: include it or exclude it. By the multiplication principle, total subsets = 2 × 2 × ... × 2 (n times) = 2^n. This includes the empty set (all elements excluded) and the full set (all elements included).

❓ Predict Output

intermediate

Trace Backtracking Subset Generation

What does this C# code output for nums = [1, 2]?

DSA C#

void Generate(int[] nums, int start, List<int> curr, List<List<int>> res) {
    res.Add(new List<int>(curr));
    for (int i = start; i < nums.Length; i++) {
        curr.Add(nums[i]);
        Generate(nums, i + 1, curr, res);
        curr.RemoveAt(curr.Count - 1);
    }
}
var result = new List<List<int>>();
Generate(new int[]{1,2}, 0, new List<int>(), result);
Console.WriteLine(result.Count);

A 4

B 3

C 2

D 6

💡 Hint

2^2 = 4 subsets for 2 elements: {}, {1}, {2}, {1,2}.

Trace: start=0, curr=[] → add []. i=0: add 1→curr=[1], recurse start=1 → add [1]. i=1: add 2→curr=[1,2] → add [1,2]. Backtrack→curr=[1]. Backtrack→curr=[]. i=1: add 2→curr=[2] → add [2]. Backtrack→curr=[]. Total: 4 subsets → output 4.

🧠 Conceptual

intermediate

Why Copy the List Before Adding

In C# subset generation, why must we write res.Add(new List(curr)) instead of res.Add(curr)?

A curr is a reference type — without copying, all entries in res would point to the same list and reflect the final state of curr

B new List<int>(curr) is faster than adding curr directly

C The result list only accepts copies, not references

D curr must be converted to List<int> before adding

💡 Hint

In C#, List is a reference type. What happens when the same object is modified after being added to another collection?

List is a reference type in C#. If you write res.Add(curr), you add a reference to the same curr list. As backtracking continues, curr is modified — elements added and removed. All entries in res that reference curr will reflect these changes, so at the end all entries show curr's final state (empty). new List(curr) creates an independent copy capturing the current state.

🔧 Debug

intermediate

Identify the Duplicate Subset Bug

This code generates duplicate subsets. Which line causes the bug?

DSA C#

void Generate(int[] nums, int start, List<int> curr, List<List<int>> res) {
    res.Add(new List<int>(curr));
    for (int i = 0; i < nums.Length; i++) {  // LINE A
        curr.Add(nums[i]);
        Generate(nums, i + 1, curr, res);    // LINE B
        curr.RemoveAt(curr.Count - 1);
    }
}

A The RemoveAt call should be removed

B LINE B — should pass i instead of i+1

C LINE A — loop should start from 'start', not 0

D res.Add should be inside the loop

💡 Hint

What happens when i starts from 0 instead of start? Can element at index 0 appear after element at index 2?

Starting from i=0 instead of start means at each recursive level we can re-pick elements that were already chosen at a higher level. This generates subsets like [2,1] (which is a duplicate of [1,2] for sets). The loop must start from 'start' to ensure each element is only considered in its original order — preventing both duplicates and out-of-order subsets.

🚀 Application

hard

Subsets with Duplicates

For nums = [1, 2, 2], how many distinct subsets does the standard powerset algorithm produce (after sorting and deduplication at each recursive level)?

A 8

B 3

C 4

D 6

💡 Hint

List the distinct subsets: {}, {1}, {2}, {1,2}, {2,2}, {1,2,2}.

The distinct subsets of [1,2,2] are: {} (empty), {1}, {2}, {2,2}, {1,2}, {1,2,2} — 6 total. The standard approach sorts the array and skips nums[i] if i > start and nums[i] == nums[i-1] at each level to avoid generating the same subset twice from duplicate elements.

Practice

1. What does the term powerset mean in the context of subsets?

easy

A. Only the subsets with even number of elements

B. All possible subsets of a given set including empty and full set

C. Subsets that contain only one element

D. Subsets that exclude the empty set

Solution

1. Step 1: Understand the definition of powerset

   The powerset of a set is the collection of all subsets, including the empty set and the set itself.

2. Step 2: Compare options with definition

   All possible subsets of a given set including empty and full set correctly describes all subsets including empty and full set. Other options limit subsets incorrectly.

3. Final Answer:

   All possible subsets of a given set including empty and full set -> Option B

4. Quick Check:

   powerset = all subsets [OK]

Hint: Powerset means every subset possible, including empty [OK]

Common Mistakes:

• Thinking powerset excludes empty set
• Confusing powerset with subsets of fixed size
• Ignoring the full set as a subset

2. Which of the following C# code snippets correctly initializes an empty list of subsets for generating a powerset?

easy

A. var subsets = new List();

B. var subsets = new List<int>();

C. var subsets = new List();

D. var subsets = new List<int>(); subsets.Add(new List<int>());

Solution

1. Step 1: Identify the correct data structure for subsets

   Each subset is a list of integers, so the collection of subsets should be a list of lists of integers.

2. Step 2: Check each option's type

   var subsets = new List(); uses List, which is correct. var subsets = new List<int>(); is List<int> (single list), var subsets = new List(); is List (array instead of list), var subsets = new List<int>(); subsets.Add(new List<int>()); mixes types incorrectly.

3. Final Answer:

   var subsets = new List(); -> Option A

4. Quick Check:

   List of list<int> for subsets [OK]

Hint: Use List to hold all subsets [OK]

Common Mistakes:

• Using List<int> instead of List
• Confusing arrays with lists
• Adding elements before initializing list

3. What is the output of the following C# code snippet?

var nums = new int[] {1, 2};
var subsets = new List { new List<int>() };
foreach (var num in nums) {
  int count = subsets.Count;
  for (int i = 0; i < count; i++) {
    var newSubset = new List<int>(subsets[i]) { num };
    subsets.Add(newSubset);
  }
}
foreach (var subset in subsets) {
  Console.Write(string.Join(",", subset) + "|");
}

medium

A. | |1|2|

B. |1|2|1,2|

C. | |1|2|1,2|

D. |1|2|

Solution

1. Step 1: Trace initial subsets list

   Initially subsets contains one empty list: [[]].

2. Step 2: Process first number 1

   For num=1, we add subsets: [1] to subsets. Now subsets = [[], [1]].

3. Step 3: Process second number 2

   For num=2, we add subsets: [2] and [1,2]. Now subsets = [[], [1], [2], [1,2]].

4. Step 4: Print all subsets

   Empty subset prints as "|", so output is "| |1|2|1,2|".

5. Final Answer:

   | |1|2|1,2| -> Option C

6. Quick Check:

   All subsets printed with empty first [OK]

Hint: Empty subset prints as empty string before others [OK]

Common Mistakes:

• Ignoring empty subset in output
• Not copying subsets before adding new element
• Miscounting subsets during iteration

4. Identify the error in the following C# code for generating subsets:

var nums = new int[] {1, 2};
var subsets = new List();
foreach (var num in nums) {
  int count = subsets.Count;
  for (int i = 0; i < count; i++) {
    var newSubset = new List<int>(subsets[i]) { num };
    subsets.Add(newSubset);
  }
}

medium

A. subsets list is not initialized with empty subset

B. Using List<int> instead of List

C. Incorrect loop range in inner for loop

D. Adding elements to subsets inside foreach causes runtime error

Solution

1. Step 1: Check initialization of subsets

   subsets is empty initially, so count is 0 and inner loop never runs.

2. Step 2: Understand consequence

   Without starting with empty subset, no new subsets are generated.

3. Final Answer:

   subsets list is not initialized with empty subset -> Option A

4. Quick Check:

   Empty subset needed to start [OK]

Hint: Always start subsets with empty list to generate powerset [OK]

Common Mistakes:

• Not adding empty subset before loop
• Assuming subsets auto-initialize
• Modifying list while iterating without base case

5. Given a list nums = new List<int> {1, 2, 2}, which modification to the standard powerset generation code will correctly generate all unique subsets without duplicates?

hard

A. Use a HashSet to store subsets as strings to avoid duplicates

B. Add all subsets without any check; duplicates will be filtered later

C. Use a Dictionary to map counts and generate subsets

D. Sort nums and skip adding duplicate elements in inner loop

Solution

1. Step 1: Understand duplicate problem

   Input has duplicates (2 appears twice), so normal powerset code generates duplicate subsets.

2. Step 2: Identify correct approach

   Sorting nums allows skipping duplicates during subset generation to avoid repeated subsets.

3. Step 3: Evaluate options

   Sort nums and skip adding duplicate elements in inner loop correctly describes sorting and skipping duplicates. Use a HashSet to store subsets as strings to avoid duplicates is workaround but less efficient. Add all subsets without any check; duplicates will be filtered later allows duplicates. Use a Dictionary to map counts and generate subsets is unrelated.

4. Final Answer:

   Sort nums and skip adding duplicate elements in inner loop -> Option D

5. Quick Check:

   Sort and skip duplicates to avoid repeats [OK]

Hint: Sort input and skip duplicates while generating subsets [OK]

Common Mistakes:

• Not sorting input before generating subsets
• Trying to remove duplicates after generation
• Using complex data structures unnecessarily