Get all subsets from a set
Submitted by st on
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