Why does enumerating all subsets of n flags give 2^n results but all orderings give n!?
answer
- Count the decisions, not the outputs
- One question per flag, or one slot per position
- Does the pool shrink as you descend?
- Branching stays two, or starts at n
- A product of twos against a falling product
basics
~20 sSubsets ask one yes/no question per item: n independent binary decisions, so 2^n outcomes. Orderings fill n positions from a shrinking pool: n choices, then n-1, then n-2, down to 1, which multiplies out to n!.
solid answer
~50 sThey are two different recursion trees, not one generator wearing two hats. For subsets you walk the items once and make an include-or-exclude decision at each, giving a binary tree of depth `n` whose 2^n leaves are the subsets; the only state you carry down is the current index plus the flags chosen so far. For orderings you fill `n` positions, and at each position you may pick any item not yet placed: branching `n`, then `n-1`, down to 1, so `n!` leaves — and you must carry which items are still available, because nothing else stops you reusing one. That extra state is the tell that you are in the bigger space. The gap is brutal: at n = 10 it is 1,024 against 3,628,800; at n = 13 orderings pass six billion while subsets are still at 8,192.
go deeper
Be ready to state both counts and where they come from: two choices per item n times, versus n then n-1 then n-2 down to one. Knowing that 10 items means about a thousand subsets but over three million orderings is the concrete fact interviewers listen for.
Explain the mechanics: the branching factor, not the depth, is what differs, and the ordering search needs availability state while the subset search gets it free from the index. Show that you classify the problem shape before writing anything.
Demonstrate the practical ceiling. Say out loud where each technique dies — roughly twenty items for subsets, a dozen for orderings — and turn that into a question about the real input size before you commit to an exhaustive plan.
Own the framing decision. When a requirement implies an n! search, the job is to challenge the requirement or find a formulation that avoids enumerating orderings at all, and to say clearly what coverage the team is actually buying.
## The two state spaces Both of these are exhaustive searches built the same way — descend, make a choice, recurse, undo — but the shape of the choice at each level is completely different, and that single difference is what separates a tractable enumeration from an impossible one. **Subsets.** Take a service with `n` independent on/off feature flags and ask for every configuration. Walk the flags in a fixed order. At flag `i` there are exactly two branches: it is on, or it is off. Recurse to flag `i+1` either way. When you reach the end you have made `n` binary decisions and the accumulated set is one configuration. Multiply the branching: 2 x 2 x ... x 2, `n` times, equals **2^n**. The recursion tree is a full binary tree of depth `n`; its leaves are the outputs. Notice what state travels down that tree: the index of the flag you are currently deciding, and the set built so far. Nothing else. The index alone tells you exactly which flags remain undecided, so there is no bookkeeping about availability. Every flag is visited once on any root-to-leaf path. **Orderings.** Now take a playlist of `n` distinct tracks and ask for every play order. The tree fills positions, not items. At position 0 any of `n` tracks may go first. At position 1 any of the `n-1` remaining tracks. At position 2, `n-2`. Multiply: n x (n-1) x ... x 1 = **n!**. The tree still has depth `n`, but the branching factor shrinks as you descend instead of staying at 2. And here the state changes character: at each level you must know *which tracks are still free*, because a track picked at position 0 must not reappear at position 3. The index no longer encodes that — the same track can be chosen early or late. So an ordering search carries an availability marker per item (or destroys and restores the pool by swapping). That extra piece of state is the reliable signal that you have crossed from 2^n territory into n! territory. ## Same depth, different width A common confusion is to equate depth with cost. Both trees are `n` deep. The difference lives entirely in the branching factor, and the branching factor is what gets multiplied. Depth `n` with branching 2 is 2^n leaves; depth `n` with branching that starts at `n` is n! leaves. A candidate who says "they are basically the same recursion, one just adds a flag" has missed that the whole cost is in the width. ## How fast the gap opens | n | subsets, 2^n | orderings, n! | |---|---|---| | 5 | 32 | 120 | | 10 | 1,024 | 3,628,800 | | 13 | 8,192 | 6,227,020,800 | | 20 | 1,048,576 | astronomically larger | By n = 10 orderings already outnumber subsets by more than three thousand times. This has a practical consequence you should be able to state at a whiteboard: exhaustive subset enumeration stays runnable to roughly n = 20-25, while exhaustive ordering enumeration falls over around n = 10-12. If someone hands you a problem over 15 items and the natural formulation enumerates orderings, the formulation is wrong, not the machine. ## Node count versus leaf count The outputs are the leaves, but the work is the nodes. A full binary tree of depth `n` has 2^(n+1) - 1 nodes, so subset enumeration does roughly twice the output count in decisions — the work is proportional to the output, which is the best you can hope for from an exhaustive search. Ordering enumeration is similar in spirit: the internal nodes are dominated by the last level, so the node count is a small constant times n!. In both cases you cannot beat the output size, which is precisely why the only real lever is *not producing the whole output*. ## The tell in an interview When you are asked to enumerate something, decide first which of the two shapes you are in, and say so out loud: - **Per-item independent decision, order irrelevant** — subset shape, 2^n, no availability state needed. - **Positions filled from a shrinking pool, order matters** — ordering shape, n!, availability state required. - **Fixed-size selection, order irrelevant** — the third member of the family, and its output count sits between the two. Getting this classification right in the first thirty seconds is most of the battle: it fixes your state, your termination condition, and your honest answer when the interviewer asks what happens at n = 30.
- Is the depth of the two recursion trees different?No — both are depth n. The subset tree makes one decision per item; the ordering tree fills one position per level, and there are n positions. The entire cost difference comes from the branching factor: a constant 2 at every level versus a factor that starts at n and shrinks. Depth is not where the explosion lives.
- Why does subset enumeration need no availability marker at all?Because each item is decided exactly once on the way down, in a fixed order. The current index already says which items are still undecided, so there is nothing to mark and nothing to unmark. Ordering enumeration loses that guarantee — an item can be chosen at any position — so it has to track availability explicitly.
- How many nodes, not leaves, does the include-exclude subset tree contain?A full binary tree of depth n has 2^(n+1) - 1 nodes, so the decision count is roughly twice the number of subsets. The search is output-bounded: you do a constant amount of work per result. That is the ceiling for any exhaustive enumeration, and it is why the only meaningful optimisation is producing fewer results.
Choosing which toppings go on a pizza is a yes/no per topping. Deciding the running order of the bands at a festival is a different job entirely: every slot you fill removes a band from the pool for every later slot.
saying these in an interview costs you the question
- Calls subsets and orderings the same generator with a flag
- Claims both trees have 2^n leaves
- Thinks 2^n eventually overtakes n!
- Forgets orderings must track which items remain
- Confuses tree depth with output count