The power set
Given a set of distinct elements, the power set is the collection of all its subsets, including the empty set and the full set. For a set of size n there are exactly two to the power n subsets, because each element is independently either in or out.
Two natural framings
- Binary choice per element: walk the elements in order and, at each one, branch twice, once including it and once skipping it. When you run past the last element, the current accumulator is one subset.
- Start index expansion: keep a running prefix and a start index. Add the prefix to the output, then loop over remaining elements, each time extending the prefix and recursing with the next index.
Both produce every subset exactly once. The start-index form naturally avoids duplicate subsets that differ only by ordering.
Avoiding duplicates
If the input contains repeated values, sort first and skip a candidate when it equals the previous one at the same recursion level. That collapses subsets that would otherwise repeat.
Key idea
Each element is an independent in-or-out decision, so the subsets form a binary tree of depth n whose leaves are the two to the power n members of the power set.