Given a set of n
distinct elements, the power set is the set of all possible subsets, including the empty set and the set itself.
Your task is to generate and return all subsets of the given set.
#include <stdio.h>
#include <math.h>
void printPowerSet(int* set, int set_size) {
unsigned int pow_set_size = 1 << set_size; // 2^n
int counter, j;
for(counter = 0; counter < pow_set_size; counter++) {
printf("{ ");
for(j = 0; j < set_size; j++) {
if (counter & (1 << j)) {
printf("%d ", set[j]);
}
}
printf("}\n");
}
}
int main() {
int set[] = {1, 2, 3};
int set_size = sizeof(set)/sizeof(set[0]);
printPowerSet(set, set_size);
return 0;
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(n * 2^n) | Even in the best case, to generate the full power set, we must iterate over all 2^n subsets, and for each subset, potentially include up to n elements based on the bitmask. So the time complexity is O(n * 2^n) in all cases. |
Average Case | O(n * 2^n) | The average case still requires generating all possible subsets (2^n), and for each subset, checking each of the n bits to determine which elements to include. Thus, the total work is proportional to n * 2^n. |
Worst Case | O(n * 2^n) | There is no way to skip subsets, so even in the worst case, the algorithm has to evaluate all 2^n combinations and for each one, examine all n bits. This results in a worst-case time complexity of O(n * 2^n). |
Comments
Loading comments...