1. One-Liner
Each integer mask from 0 to 2^n−1 encodes one subset: bit i means take element i.
2. The Problem It Solves
Generate subsets for brute-force small n, competitive programming, and DP over subsets (SOS DP builds on this idea).
3. The Core Idea
Nested loops: outer mask, inner bit scan to collect members—natural order Gray code can minimize transitions (see Gray code).
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | n = len(arr) |
| 2 | For mask in 0..2^n-1 |
| 3 | For each bit i in mask, if set include arr[i] |
| 4 | Collect subset |
5. Dry Run Example
n=3 → 8 subsets from {} to {a,b,c} following binary masks.
6. Key Properties
| Property | Detail |
|---|---|
| Count | 2^n subsets |
| Order | Binary mask order |
| Pruning | Add constraints inside loop |
7. Where It Is Used
| Domain / System | Use |
|---|---|
| Scheduling | Feasible subsets |
| Testing | Combinatorial cases |
| Crypto | Tiny exhaustive search |
8. Interview Tips
For n>20 brute force explodes—meet-in-the-middle or DP. Mention Gosper’s hack for k-bit sets.
9. Comparison with Other Algorithms
| Technique | Notes |
|---|---|
| Recursion backtracking | Same 2^n |
| Branch & bound | Prune early |
| SOS DP | Sum over supersets |
10. Complexity
| -- | -- |
|---|---|
| Time | O(n · 2^n) |
| Space | O(n) per subset output |
Implementation Example (PYTHON)
def power_set(arr):
n = len(arr)
out = []
for mask in range(1 << n):
sub = [arr[i] for i in range(n) if mask >> i & 1]
out.append(sub)
return out