#include <stdio.h>
// The power set of a set S is the set of all subsets of S, written as P(S).
/*
Function: generatePowerSet
Purpose: Print the power set of an integer array using bit manipulation.
Explanation of algorithm:
- A set with n elements has 2^n subsets.
- Each number from 0 to (2^n - 1) represents one subset.
- Each bit in that number tells us whether to include the corresponding element.
Example for n = 4:
mask = 5 → binary 0101 → include elements at positions 0 and 2.
*/
void generatePowerSet(const int *set, int n) {
int totalSubsets = 1 << n; /* 2^n subsets */
for (int mask = 0; mask < totalSubsets; mask++) {
printf("{ ");
/* Check each bit of mask */
for (int bit = 0; bit < n; bit++) {
if (mask & (1 << bit)) {
printf("%d ", set[bit]);
}
}
printf("}\n");
}
}
int main(void) {
int inputSet[] = {1, 2, 3, 4};
int n = sizeof(inputSet) / sizeof(inputSet[0]);
printf("Power set of {1,2,3,4}:\n");
generatePowerSet(inputSet, n);
return 0;
}
/*
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 }
*/
