Power Set (Subsets)
WHAT IT SAYS
Return every possible subset of an array of distinct integers.
WHAT IT'S REALLY ASKING
"Every element faces exactly one question, and it never has to answer twice: in, or out? Line those n answers up in a row and a subset stops being something you search for — it is an n-bit number, and you already know how to count."
Permute, then collapse into a set
O(n! * n) time, plus a set holding every duplicate you makeGenerate every arrangement of every length, sort each one so that [1,2] and [2,1] look alike, and throw them into a hash set until the duplicates stop appearing.
WHERE THE WORK IS WASTED — You are enumerating ORDERINGS to produce things that have no order. For n = 10 there are over 3.6 million permutations and exactly 1024 subsets — so roughly 99.97 percent of everything you construct is a repeat of something you already have, and you pay a sort plus a hash on each one just to discover that. The duplication is not a bug in the loop; it is the loop answering a question nobody asked.
No element's decision constrains any other element's.
Read the problem statement again and notice what is NOT in it: there is no constraint. Nothing says that taking element 3 forbids element 5, or that the subset must sum to something, or that it must have a certain size. Every element's fate is decided in complete isolation. When n decisions are independent and each has 2 outcomes, the set of outcomes is a product space — and a product space is not searched, it is COUNTED. Its size is exactly 2^n, which is a proof of the answer count before you write a line of code. And every decision vector is realised by exactly one combination of choices, so distinct choice-vectors give distinct subsets. Duplicates cannot occur. Not 'are filtered out' — cannot occur. That immediately hands you an enumeration. The integers 0 through 2^n - 1, written in binary, ARE the decision vectors: bit i answers 'is element i in?'. Counting from 0 upward walks every vector exactly once, in a total order, with no bookkeeping whatsoever. The odometer is the algorithm. The recursive pick / do-not-pick formulation is the same product space, walked depth-first instead of by counting. Same tree, same 2^n leaves — just a different traversal order.
Count to 2^n, or recurse pick / skip
O(2^n * n) time, O(n) extra space for the recursion or the maskIteratively: for mask from 0 to 2^n - 1, collect every element whose bit is set in mask. Recursively: at index i, branch on including a[i] and on excluding it, and record the path when i runs off the end. Either way the cost is O(2^n * n), which is optimal — the output itself has that many characters in it.
Independent Binary Choices
YOU'LL SEE IT AGAIN WHEN
- Each element has a small fixed menu of options and no option constrains any other element — there is no constraint to check anywhere.
- The output size is inherently exponential, so the goal is not to beat it but to hit it exactly: no duplicates generated, no candidates rejected.
- The answers can be indexed by a counter — a bitmask, or a mixed-radix number — which means enumeration replaces search entirely.