#include <iostream>
#include <vector>
// The power set of a set S is the set of all subsets of S, written as P(S).
/*
Function: generatePowerSet
Purpose: Create the power set of a given vector<int> using bit manipulation.
This is efficient because each subset corresponds to a unique binary
representation of numbers from 0 to (2^n - 1).
Explanation of algorithm:
- For a set of size n, there are 2^n possible subsets.
- Each number from 0 to (2^n - 1) represents one subset.
- For each bit position j in number i:
- If bit j is ON (i.e., (i & (1 << j)) != 0), include element[j] in the subset.
*/
std::vector<std::vector<int>> generatePowerSet(const std::vector<int>& set) {
std::vector<std::vector<int>> powerSet;
int n = set.size();
int totalSubsets = 1 << n; // 2^n subsets
for (int mask = 0; mask < totalSubsets; ++mask) {
std::vector<int> subset;
// Check each bit of mask
for (int bit = 0; bit < n; ++bit) {
if (mask & (1 << bit)) {
subset.push_back(set[bit]);
}
}
powerSet.push_back(subset);
}
return powerSet;
}
int main() {
std::vector<int> inputSet = {1, 2, 3, 4};
// Generate the power set
std::vector<std::vector<int>> result = generatePowerSet(inputSet);
// Print the power set
std::cout << "Power set of {1,2,3,4}:\n";
for (const auto& subset : result) {
std::cout << "{ ";
for (int num : subset) {
std::cout << num << " ";
}
std::cout << "}\n";
}
}
/*
run:
Power set of {1,2,3,4}:
{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
{ 1 3 }
{ 2 3 }
{ 1 2 3 }
{ 4 }
{ 1 4 }
{ 2 4 }
{ 1 2 4 }
{ 3 4 }
{ 1 3 4 }
{ 2 3 4 }
{ 1 2 3 4 }
*/
