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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Powerset Generation with Recursion

What is the output of the following C++ code that generates all subsets (powerset) of the set {1, 2}?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void generateSubsets(vector<int>& nums, int index, vector<int>& current, vector<vector<int>>& result) {
    if (index == nums.size()) {
        result.push_back(current);
        return;
    }
    // Include nums[index]
    current.push_back(nums[index]);
    generateSubsets(nums, index + 1, current, result);
    // Exclude nums[index]
    current.pop_back();
    generateSubsets(nums, index + 1, current, result);
}

int main() {
    vector<int> nums = {1, 2};
    vector<vector<int>> result;
    vector<int> current;
    generateSubsets(nums, 0, current, result);
    for (auto& subset : result) {
        cout << "[";
        for (int i = 0; i < subset.size(); i++) {
            cout << subset[i];
            if (i != subset.size() - 1) cout << ", ";
        }
        cout << "]\n";
    }
    return 0;
}

A

[1]
[2]
[]
[1, 2]

B

[]
[1]
[2]
[1, 2]

C

[]
[2]
[1]
[1, 2]

D

[1, 2]
[1]
[2]
[]

💡 Hint

Think about the order subsets are added when including or excluding elements recursively.

The recursion explores the include branch first, adding [1, 2] , then backtracks to [1], then excludes 1 to add [2] and [], resulting in the order: [1, 2], [1], [2], [].

🧠 Conceptual

intermediate

Number of Subsets in Powerset

Given a set with 5 distinct elements, how many subsets does its powerset contain?

A 32

B 16

C 10

D 25

💡 Hint

Each element can either be in or out of a subset.

For a set with n elements, the powerset contains 2^n subsets. For n=5, 2^5 = 32.

🔧 Debug

advanced

Identify the Error in Powerset Code

What error will the following C++ code produce when generating all subsets of {1, 2}?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void generateSubsets(vector<int>& nums, int index, vector<int>& current, vector<vector<int>>& result) {
    if (index > nums.size()) {
        result.push_back(current);
        return;
    }
    current.push_back(nums[index]);
    generateSubsets(nums, index + 1, current, result);
    current.pop_back();
    generateSubsets(nums, index + 1, current, result);
}

int main() {
    vector<int> nums = {1, 2};
    vector<vector<int>> result;
    vector<int> current;
    generateSubsets(nums, 0, current, result);
    for (auto& subset : result) {
        cout << "[";
        for (int i = 0; i < subset.size(); i++) {
            cout << subset[i];
            if (i != subset.size() - 1) cout << ", ";
        }
        cout << "]\n";
    }
    return 0;
}

A Runtime error: out_of_range exception

B Syntax error: missing semicolon

C Infinite recursion causing stack overflow

D No error, outputs all subsets correctly

💡 Hint

Check the base case condition for index.

The base case checks if index > nums.size(), but valid indices are 0 to nums.size()-1. Accessing nums[index] when index == nums.size() causes out_of_range exception.

🚀 Application

advanced

Find Subsets with Sum Equal to Target

Given the set {1, 2, 3} and target sum 3, which subsets from the powerset sum exactly to 3?

A [1, 2, 3]

B [3], [1, 2]

C [1, 3], [2, 3]

D [2], [3]

💡 Hint

Check sums of all subsets carefully.

Subsets summing to 3 are [3] and [1, 2]. Others do not sum to 3.

📝 Syntax

expert

Correct Syntax for Iterative Powerset Generation

Which option correctly implements iterative generation of all subsets of {1, 2} in C++?

A

vector<vector<int>> subsets = {{};};
for (int num : nums) {
  int n = subsets.size();
  for (int i = 0; i < n; i++) {
    vector<int> set = subsets[i];
    set.push_back(num);
    subsets.push_back(set);
  }
}

B

vector<vector<int>> subsets = {{};
for (int num : nums) {
  int n = subsets.size();
  for (int i = 0; i < n; i++) {
    vector<int> set = subsets[i];
    set.push_back(num);
    subsets.push_back(set);
  }
}

C

vector<int> nums = {1, 2};
vector<vector<int>> subsets = {{}};
for (int num : nums) {
  int n = subsets.size();
  for (int i = 0; i < n; i++) {
    vector<int> set = subsets[i];
    set.push_back(num);
    subsets.push_back(set);
  }
}

D

vector<vector<int>> subsets = {};
for (int num : nums) {
  int n = subsets.size();
  for (int i = 0; i < n; i++) {
    vector<int> set = subsets[i];
    set.push_back(num);
    subsets.push_back(set);
  }
}

💡 Hint

Check the initialization of subsets vector and syntax of braces.

Option C correctly initializes subsets with one empty subset using {{}} and has correct braces. Others have syntax errors or wrong initialization.

Practice

1. What does the "Generate All Subsets (Powerset)" algorithm produce when given a set {1, 2}?

easy

A. Only subsets with two elements: {1, 2}

B. All possible subsets including empty set: {}, {1}, {2}, {1, 2}

C. Only subsets with one element: {1}, {2}

D. Only the empty set: {}

Solution

1. Step 1: Understand what subsets mean

   Subsets include all combinations of elements, from empty to full set.

2. Step 2: List all subsets of {1, 2}

   They are {}, {1}, {2}, and {1, 2}.

3. Final Answer:

   All possible subsets including empty set: {}, {1}, {2}, {1, 2} -> Option B

4. Quick Check:

   Subsets = all combinations [OK]

Hint: Remember powerset includes empty and full sets [OK]

Common Mistakes:

• Thinking subsets only have full or single elements
• Ignoring the empty subset
• Confusing subsets with permutations

2. Which of the following C++ code snippets correctly initializes an empty vector of vectors to store subsets?

easy

A. std::vector<int> subsets;

B. std::vector subsets = {{}};

C. std::vector subsets;

D. std::vector subsets<int>;

Solution

1. Step 1: Identify correct vector declaration

   We need a vector of vectors of int to store subsets.

2. Step 2: Check syntax correctness

   std::vector subsets; uses correct syntax: std::vector subsets; initializes empty vector of vectors.

3. Final Answer:

   std::vector subsets; -> Option C

4. Quick Check:

   Correct vector of vectors syntax [OK]

Hint: Use vector for subsets storage [OK]

Common Mistakes:

• Using vector<int> instead of vector
• Incorrect template syntax like vector subsets<int>
• Trying to initialize with empty braces incorrectly

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

std::vector<int> nums = {1, 2};
std::vector subsets = {{}};
for (int num : nums) {
    int n = subsets.size();
    for (int i = 0; i < n; i++) {
        std::vector<int> newSubset = subsets[i];
        newSubset.push_back(num);
        subsets.push_back(newSubset);
    }
}
for (auto &subset : subsets) {
    for (int x : subset) std::cout << x << " ";
    std::cout << "| ";
}

medium

A. | | 1 | 2 | 1 2 |

B. | | 1 2 | 1 | 2 |

C. | 1 | 2 | 1 2 |

D. | 1 2 | 1 | 2 |

Solution

1. Step 1: Understand initial subsets and loop

   Initially subsets = {{}}, empty subset only. For each num, we add new subsets by adding num to existing subsets.

2. Step 2: Trace iterations

   For num=1: subsets become {}, {1}. For num=2: subsets become {}, {1}, {2}, {1, 2}.

3. Final Answer:

   | | 1 | 2 | 1 2 | -> Option A

4. Quick Check:

   All subsets printed with spaces and separators [OK]

Hint: Start with empty subset and add elements iteratively [OK]

Common Mistakes:

• Missing the empty subset in output
• Printing subsets in wrong order
• Confusing push_back inside loop

4. Identify the error in this C++ code snippet for generating subsets:

std::vector<int> nums = {1, 2};
std::vector subsets;
for (int num : nums) {
    int n = subsets.size();
    for (int i = 0; i < n; i++) {
        std::vector<int> newSubset = subsets[i];
        newSubset.push_back(num);
        subsets.push_back(newSubset);
    }
}

medium

A. subsets vector is not initialized with empty subset before loop

B. Loop variable i should start from 1, not 0

C. newSubset.push_back(num) should be outside inner loop

D. nums vector should be empty to generate subsets

Solution

1. Step 1: Check initialization of subsets

   subsets is empty initially, so subsets.size() is 0, inner loop never runs.

2. Step 2: Identify missing empty subset

   We must start subsets with empty subset {{}} to build new subsets correctly.

3. Final Answer:

   subsets vector is not initialized with empty subset before loop -> Option A

4. Quick Check:

   Empty subset needed to start building subsets [OK]

Hint: Always start subsets with empty subset {{}} [OK]

Common Mistakes:

• Not initializing subsets with empty subset
• Changing loop start index incorrectly
• Misplacing push_back calls

5. Given a vector nums = {1, 2, 2}, which code modification ensures the generated subsets contain no duplicate subsets?

hard

A. Generate subsets normally; duplicates are impossible with vector<int>.

B. Use a set to store subsets after generation to remove duplicates.

C. Ignore duplicate elements in nums vector before generating subsets.

D. Sort nums first and skip adding duplicates during subset generation.

Solution

1. Step 1: Understand duplicates in input

   Input has duplicate 2's, so subsets like {2} can appear multiple times.

2. Step 2: Use sorting and skip duplicates

   Sorting nums helps detect duplicates; skip adding subsets with same element consecutively to avoid duplicates.

3. Final Answer:

   Sort nums first and skip adding duplicates during subset generation. -> Option D

4. Quick Check:

   Sorting + skipping duplicates avoids repeated subsets [OK]

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

Common Mistakes:

• Assuming duplicates never occur
• Removing duplicates from input loses valid subsets
• Using set after generation is less efficient