C++ Program to Find All Subsets of a Set

Use a recursive function in C++ that explores including or excluding each element to find all subsets; for example, void findSubsets(vector& nums, vector& current, int index) recursively builds subsets by choosing to add or skip elements.

Examples

Inputnums = {1}

Output{} {1}

Inputnums = {1, 2}

Output{} {1} {2} {1, 2}

Inputnums = {}

Output{}

How to Think About It

To find all subsets, think of each element as having two choices: either it is included in the current subset or it is not. By exploring both choices for every element, you generate all possible combinations. This can be done by moving through the list one element at a time and recursively building subsets.

Algorithm

1

Start with an empty subset and the first element index.

2

At each step, decide to include the current element in the subset or skip it.

3

Recursively repeat this for the next element index.

4

When the index reaches the end of the list, record the current subset.

5

Return all recorded subsets after exploring all choices.

Code

cpp

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

void findSubsets(const vector<int>& nums, vector<int>& current, int index) {
    if (index == nums.size()) {
        cout << "{";
        for (int i = 0; i < current.size(); ++i) {
            cout << current[i];
            if (i != current.size() - 1) cout << ", ";
        }
        cout << "}\n";
        return;
    }
    // Exclude current element
    findSubsets(nums, current, index + 1);
    // Include current element
    current.push_back(nums[index]);
    findSubsets(nums, current, index + 1);
    current.pop_back();
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<int> current;
    findSubsets(nums, current, 0);
    return 0;
}

Output

{}
{3}
{2}
{2, 3}
{1}
{1, 3}
{1, 2}
{1, 2, 3}

Dry Run

Let's trace the example nums = {1, 2} through the code

1

Start with index 0 and empty subset

current = {}, index = 0

2

Exclude nums[0] = 1 and move to index 1

current = {}, index = 1

3

Exclude nums[1] = 2 and move to index 2 (end)

current = {}, index = 2 -> print {}

4

Include nums[1] = 2 and move to index 2 (end)

current = {2}, index = 2 -> print {2}

5

Back to index 0, include nums[0] = 1

current = {1}, index = 1

6

Exclude nums[1] = 2 and move to index 2 (end)

current = {1}, index = 2 -> print {1}

7

Include nums[1] = 2 and move to index 2 (end)

current = {1, 2}, index = 2 -> print {1, 2}

Step	Current Subset	Index
1	{}	0
2	{}	1
3	{}	2 (print {})
4	{2}	2 (print {2})
5	{1}	1
6	{1}	2 (print {1})
7	{1, 2}	2 (print {1, 2})

Why This Works

Step 1: Recursive exploration

The function uses recursion to explore two paths at each element: including it or excluding it, which ensures all subsets are covered.

Step 2: Base case prints subset

When the index reaches the end of the list, the current subset is printed, representing one complete subset.

Step 3: Backtracking

After exploring including an element, the code removes it (backtracks) to explore other subsets without that element.

Alternative Approaches

Bitmasking

cpp

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

int main() {
    vector<int> nums = {1, 2, 3};
    int n = nums.size();
    int total = 1 << n; // 2^n subsets
    for (int mask = 0; mask < total; ++mask) {
        cout << "{";
        bool first = true;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                if (!first) cout << ", ";
                cout << nums[i];
                first = false;
            }
        }
        cout << "}\n";
    }
    return 0;
}

This method uses binary numbers to represent subsets and is iterative, which can be faster but less intuitive than recursion.

Iterative subset building

cpp

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

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

This builds subsets iteratively by adding each element to existing subsets, which is easy to understand and avoids recursion.

Complexity: O(n * 2^n) time, O(n) space

Time Complexity

There are 2^n subsets for n elements, and printing each subset takes up to O(n) time, so total time is O(n * 2^n).

Space Complexity

The recursion stack and current subset use O(n) space, as at most n elements are stored at once.

Which Approach is Fastest?

Bitmasking is often faster due to iteration and bit operations, but recursion is easier to understand and modify.

Approach	Time	Space	Best For
Recursive Backtracking	O(n * 2^n)	O(n)	Clear logic, easy to modify
Bitmasking	O(n * 2^n)	O(n)	Performance and iteration
Iterative Building	O(n * 2^n)	O(n * 2^n)	Avoid recursion, build subsets stepwise