Power Set

Problem Statement❯

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.

Examples❯

Input Set	Output	Description
[1, 2]	[[], [1], [2], [1, 2]]	Normal case with 2 elements; generates 2^2 = 4 subsets
[0, 1, 2]	[[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]]	3 elements; generates 2^3 = 8 subsets using binary representation
[]	[[]]	Edge case with empty input; power set contains only the empty set
["a"]	[[], ["a"]]	Single element set; two subsets: empty and the element itself
[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]]	Power set of 4 elements contains 2^4 = 16 subsets
["x", "y"]	[[], ["x"], ["y"], ["x", "y"]]	Supports string elements as well; binary selection works the same
[""]	[[], [""]]	Edge case where set has an empty string; still valid element
null	[[]]	Null treated as empty set; power set is [[]]
[1, 2, 3, 4, 5]	32 subsets	Larger normal case; 5 elements generate 2^5 = 32 subsets
[100]	[[], [100]]	Single large number; still produces 2 subsets

Solution❯

Understanding the Problem

We are given a set of n distinct elements, and we are asked to generate its power set. A power set is the collection of all possible subsets that can be formed from the given set — including the empty set and the set itself.

For example, if the input set is [a, b], the power set would be [[], [a], [b], [a, b]].

This is a common problem in combinatorics and programming, and it can be solved efficiently using bit manipulation.

Step-by-Step Solution with Example

Step 1: Understand how subsets relate to binary numbers

Each element in the original set has two choices: either it is present in a subset or it is not. So, for n elements, there are 2^n possible combinations — which means 2^n subsets.

We can represent each subset using a binary number where the i-th bit tells whether to include the i-th element.

Step 2: Take an example set [1, 2, 3]

The size of the input set is 3, so total subsets = 2^3 = 8. We loop from 0 to 7, and for each number, we check its binary representation.

0 → 000 → []
1 → 001 → [3]
2 → 010 → [2]
3 → 011 → [2, 3]
4 → 100 → [1]
5 → 101 → [1, 3]
6 → 110 → [1, 2]
7 → 111 → [1, 2, 3]

We interpret each bit from right to left (LSB to MSB) and use it to decide whether to include the corresponding element from the input set.

Step 3: Implement the logic in code

def power_set(nums):
    n = len(nums)
    result = []
    total = 1 << n  # 2^n subsets

    for mask in range(total):
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])
        result.append(subset)

    return result

# Example:
print(power_set([1, 2, 3]))

Edge Cases

Empty Set: If the input is [], the power set should return [[]].
Single Element: Input [x] should return [[], [x]].
Large Input Size: Since total subsets = 2^n, be careful if n is large (e.g., > 20), as it could cause performance or memory issues.

Final Thoughts

This problem gives a great opportunity to practice bit manipulation and understand how binary numbers can represent subset selections. It's also a common pattern in backtracking and dynamic programming problems.

By understanding this step-by-step process, even beginners can break down and solve more complex combinatorics problems later on.

Algorithm Steps❯

The total number of subsets for a set of size n is 2^n.
Loop through all numbers from 0 to 2^n - 1. Each number represents a subset.
For each number, check the binary representation. If the j-th bit is set, include the j-th element of the original set in the current subset.
Collect all such subsets into the result list.

Code

C++

Python

Java

Rust

Kotlin

Swift

#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;
}

Time Complexity❯

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).

Space Complexity❯

O(n * 2^n)

Explanation: The output contains all 2^n subsets, and each subset can contain up to n elements. Hence, the space required to store the result is O(n * 2^n). Additional space usage is minimal compared to the output size.