Question

How to get all possible subsets from a given group of numbers in C++

Answer 1

#include <iostream>
#include <vector>

using std::vector;

// Generate all subsets (the power set) of a given list of numbers.
// This implementation uses bitmasking
// For a list of size n, every subset corresponds to a binary number
// from 0 to (2^n - 1). Each bit indicates whether an element is included.

vector<vector<int>> subsets(const vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> result;

    // Loop over all possible bitmasks from 0 to 2^n - 1
    for (int mask = 0; mask < (1 << n); mask++) {

        vector<int> subset;

        // Check each bit position
        for (int i = 0; i < n; i++) {

            // If the i-th bit of mask is set, include nums[i]
            if (mask & (1 << i)) {
                subset.push_back(nums[i]);
            }
        }

        // Add the constructed subset to the result list
        result.push_back(subset);
    }

    return result;
}

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

    // Generate all subsets of nums
    auto res = subsets(nums);

    // Print each subset in a readable format
    for (auto& s : res) {
        std::cout << "{ ";
        for (int x : s) std::cout << x << " ";
        std::cout << "}\n";
    }
}



/*
run:

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

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <vector>

using std::vector;

// Backtracking function to build all subsets.
// index  – the next position in nums we are allowed to use
// nums   – the original input list
// current – the subset being built at this moment
// result – all completed subsets collected here
void backtrack(int index, const vector<int>& nums, vector<int>& current, vector<vector<int>>& result) {
    // Every state of "current" is a valid subset, so store it
    result.push_back(current);

    // Try adding each remaining element one by one
    for (int i = index; i < nums.size(); i++) {

        // Choose nums[i]
        current.push_back(nums[i]);

        // Explore further subsets that include nums[i]
        backtrack(i + 1, nums, current, result);

        // Undo the choice (backtrack)
        current.pop_back();
    }
}

// Wrapper function that initializes the process
vector<vector<int>> subsets(const vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> current;

    // Start building subsets from index 0
    backtrack(0, nums, current, result);

    return result;
}

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

    // Generate all subsets
    auto res = subsets(nums);

    // Print them nicely
    for (auto& s : res) {
        std::cout << "{ ";
        for (int x : s) std::cout << x << " ";
        std::cout << "}\n";
    }
}



/*
run:

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

*/

 

70+ SQL courses for beginners and professionals

Answer 3

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

// Generate all subsets using an iterative approach.
// Idea:
// Start with one subset: the empty set {}.
// For each number in nums, duplicate all existing subsets
// and append the number to each duplicate.
// This effectively doubles the number of subsets at every step.
vector<vector<int>> subsets(const vector<int>& nums) {
    // Start with the empty subset
    vector<vector<int>> result = {{}};

    // Process each number in the input list
    for (int num : nums) {

        // Current size before adding new subsets
        int size = result.size();

        // For each existing subset, create a new one that includes 'num'
        for (int i = 0; i < size; i++) {

            // Copy the existing subset
            auto newSubset = result[i];

            // Add the current number to it
            newSubset.push_back(num);

            // Store the new subset
            result.push_back(newSubset);
        }
    }

    return result;
}

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

    // Generate all subsets
    auto res = subsets(nums);

    // Print them in a readable format
    for (auto& s : res) {
        cout << "{ ";
        for (int x : s) cout << x << " ";
        cout << "}\n";
    }
}



/*
run:

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

*/

 

70+ SQL courses for beginners and professionals