#include <iostream>
#include <vector>
#include <string>
/*
Generate all subsets of a given set using an iterative algorithm.
Technique:
----------
We use the "bitmask" method:
- For a set of size N, there are 2^N possible subsets.
- Each subset corresponds to an integer from 0 to (2^N - 1).
- The binary representation of that integer tells us which elements
are included in the subset:
- If bit j is 1 → include element j
- If bit j is 0 → exclude element j
This approach is efficient, simple, and avoids recursion entirely.
*/
// Function that generates all subsets using bitmask iteration
std::vector<std::vector<std::string>> generateSubsets(const std::vector<std::string>& items) {
std::vector<std::vector<std::string>> allSubsets;
const std::size_t n = items.size();
const std::size_t total = 1ULL << n; // 2^n subsets
// Iterate through all bit patterns
for (std::size_t mask = 0; mask < total; ++mask) {
std::vector<std::string> subset;
// Check each bit of the mask
for (std::size_t bit = 0; bit < n; ++bit) {
if (mask & (1ULL << bit)) {
subset.push_back(items[bit]);
}
}
allSubsets.push_back(std::move(subset));
}
return allSubsets;
}
// Helper function to print all subsets
void printSubsets(const std::vector<std::vector<std::string>>& subsets) {
std::cout << "All subsets:\n";
for (const auto& subset : subsets) {
std::cout << "{ ";
for (const auto& element : subset) {
std::cout << element << " ";
}
std::cout << "}\n";
}
}
int main() {
// Example set
std::vector<std::string> items = { "A", "B", "C" };
// Generate subsets
auto subsets = generateSubsets(items);
// Print results
printSubsets(subsets);
}
/*
run:
All subsets:
{ }
{ A }
{ B }
{ A B }
{ C }
{ A C }
{ B C }
{ A B C }
*/
