How to extract all combinations (unordered subsets) from a given set in C++?

Let us estimate the count before. Suppose `N` is the size of a given set, and `K` is the number of elements in the subset. The count of all combinations (unordered subsets) of size `K` is

`C(N, K) = N! / (K! * (N - K)!)`

Then the count of all subsets is

`C(N, 1) + C(N, 2) + ... + C(N, N) = 2^N - 1`

So we expect to produce 7 subsets from a set of 3 elements, 15 subsets from 4-elements set, and so on.

``````#include <iostream>
#include <vector>

using set_t = std::vector<int>;
using subsets_t = std::vector<set_t>;

void make_combinations(const set_t& data, const size_t index, const set_t& current_subset, subsets_t& subsets)
{
for (size_t i = index; i < data.size(); i++)
{
set_t subset = current_subset;
subset.push_back(data[i]);
subsets.push_back(subset);
make_combinations(data, i + 1, subset, subsets);
}
}

subsets_t get_subsets(const set_t& data)
{
subsets_t subsets;
make_combinations(data, 0, set_t(), subsets);
return subsets;
}

void print_subsets(const subsets_t& subsets)
{
std::cout << "Subset count: " << subsets.size() << std::endl;
for (const auto& subset : subsets)
{
for (const auto value : subset)
{
std::cout << value << " ";
}
std::cout << std::endl;
}
std::cout << std::endl;
}

int main()
{
subsets_t subsets = get_subsets({ 1, 2, 3, 4 });
print_subsets(subsets);
return 0;
}
``````

Result

``````Subset count: 15
1
1 2
1 2 3
1 2 3 4
1 2 4
1 3
1 3 4
1 4
2
2 3
2 3 4
2 4
3
3 4
4
``````