#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
Generate all subsets of a set using an iterative algorithm in C.
Approach:
---------
Use the classic bitmask technique:
- For a set of size N, there are 2^N subsets.
- Each integer from 0 to (2^N - 1) represents one subset.
- The binary representation of that integer determines which
elements are included:
bit j = 1 → include element j
bit j = 0 → exclude element j
This avoids recursion and uses simple integer operations.
*/
// Function to generate and print all subsets
void generate_subsets(const char *items[], size_t count) {
size_t total = 1ULL << count; // 2^count subsets
printf("All subsets:\n");
// Iterate through all bit patterns
for (size_t mask = 0; mask < total; ++mask) {
printf("{ ");
// Check each bit of the mask
for (size_t bit = 0; bit < count; ++bit) {
if (mask & (1ULL << bit)) {
printf("%s ", items[bit]);
}
}
printf("}\n");
}
}
int main(void) {
// Example set
const char *items[] = { "A", "B", "C" };
size_t count = sizeof(items) / sizeof(items[0]);
// Generate and print subsets
generate_subsets(items, count);
return 0;
}
/*
run:
All subsets:
{ }
{ A }
{ B }
{ A B }
{ C }
{ A C }
{ B C }
{ A B C }
*/
