skip to content

A document may carry any combination of n labels — how many distinct label sets exist, and what does that rule out?

level: middleimportance: should knowfreq 50%

answer

  1. each label is an independent yes or no
  2. the count doubles per label
  3. twenty labels is already a million
  4. the empty combination counts too
  5. subsets double, pairs multiply

basics

~20 s

There are 2^n of them — the power set of the label set, including the empty combination. Because the count doubles with every label added, precomputing or caching one entry per possible label-set filter is impossible past roughly twenty labels.

solid answer

~50 s

The collection of all subsets of a set is its **power set**, and for `n` labels it has `2^n` members, counting the empty label set and the full one. The reason is one independent binary choice per label: each label is either in a given combination or out of it, so adding one more label doubles the number of combinations rather than adding to it. With 3 labels there are 8 combinations; with 20 there are 1,048,576; with 30, over a billion. That is why a design that wants one precomputed result, cache entry, permission row or materialised view **per possible label combination** collapses almost immediately, while a design that keeps one set per label and combines them with union and intersection at query time scales with `n`. Note that this is different from pairing: combining `m` labels with `k` languages gives `m × k` pairs, a product, not a power.

code

pseudocode · 10 lines
pseudocode
combinations = [ {} ]                  // start with the empty label set

for each label in labels:
    next = []
    for each c in combinations:
        next = next + [ c ]            // this combination, without the label
        next = next + [ c + {label} ]  // the same one, with it
    combinations = next

// size of combinations after each label: 1, 2, 4, 8, ... 2^n

go deeper

for a junior

Recall that the set of all subsets is the power set and that n labels give 2^n combinations, the empty one included. Be able to list all eight for three labels.

for a middle

Justify the exponent by the independent in-or-out choice per label and show the doubling, then contrast it with a Cartesian product, whose size is a product of sizes rather than a power.

for a senior

Use the number to kill a design in review: name the label count at which per-combination storage or enumeration stops being viable, and propose per-label sets combined at query time instead.

for a principal

Treat the size of the taxonomy as a design parameter with a budget. Anything whose cost is indexed by combinations rather than by labels is a commitment that a growing taxonomy will break on a schedule you do not control.

## The power set Given a set `S`, its **power set** `P(S)` is the set whose members are all the subsets of `S` — including the empty set `∅` and `S` itself. For labels `S = {urgent, invoice, 2024}` the power set has eight members: ``` {} {urgent} {invoice} {2024} {urgent, invoice} {urgent, 2024} {invoice, 2024} {urgent, invoice, 2024} ``` Eight is `2^3`. In general `|P(S)| = 2^n` where `n = |S|`. Two edges follow immediately and are worth stating: a set with no labels has a power set of size `2^0 = 1`, whose single member is the empty set, and the empty set is a member of every power set, because the empty set is a subset of every set. ## Why it doubles Building the subsets one label at a time makes the exponent obvious. Start with the list containing only the empty combination. For each label in turn, every combination built so far spawns exactly two: the one without the new label and the same one with it. Nothing is lost and nothing collides, so the list **doubles** at each step: 1, 2, 4, 8, … `2^n`. Equivalently: to name one subset you answer `n` independent yes/no questions, one per label. Independent binary choices multiply, so `n` of them give `2 × 2 × … × 2 = 2^n` distinct answers, and distinct answers give distinct subsets. ## What the growth rules out The numbers are the argument: | labels `n` | distinct label sets `2^n` | |---|---| | 3 | 8 | | 10 | 1,024 | | 20 | 1,048,576 | | 30 | 1,073,741,824 | Doubling is not 'fast growth' in the way a quadratic is fast; it outruns any polynomial in `n`, so buying bigger hardware moves the wall by one or two labels. Designs this kills: - **One precomputed result set per possible filter.** Twenty labels is already a million entries, and a taxonomy that only ever grows makes the plan worse every sprint. - **One permission row, one materialised view, or one cache key per label combination.** Same count, same wall. - **Enumerating combinations to find the best one.** Any exhaustive search over combinations is `2^n` work by construction, however tight the inner loop is. What survives is the algebra: keep **one set per label** — `n` of them, linear in the taxonomy — and compute unions, intersections and differences when a query arrives. A filter naming `k` labels then costs work proportional to the sizes of those `k` sets, and the total stored grows with the number of labels, not with the number of their combinations. ## Power set versus Cartesian product These are the two 'how many combinations' questions, and confusing them misprices a design by a wide margin. | | Power set `P(S)` | Cartesian product `A × B` | |---|---|---| | Members are | subsets of one set | ordered pairs `(a, b)` | | Size | `2^n` | the product of the two sizes | | Models | which labels a document carries | the shape of a pairing: label with language, user with document | | Growth | doubles per new label | grows by one factor's size | So 'each of 5 labels with each of 3 languages' is `5 × 3 = 15` pairs — a product, and comfortably enumerable. 'Any combination of 5 labels' is `2^5 = 32` — a power. The Cartesian product generalises to more factors the same way: three factors of sizes `a`, `b`, `c` give `a × b × c` triples, which is the shape behind any grid of dimensions, a compatibility matrix, or a relation as a set of pairs. ## What an interviewer is listening for Not the formula — the consequence. The good answer names `2^n`, justifies it by the independent per-label choice rather than by a memorised rule, and then immediately says what it forbids: no enumeration of combinations, no per-combination storage, and a taxonomy whose size must be treated as a design parameter rather than a detail. The candidate who also separates 'subsets of one set' from 'pairs from two sets' has the tool needed to size the next feature correctly instead of by feel.

  • A filter pairs each of 5 labels with each of 3 languages. How many pairs are there, and why is that not a power?
    Fifteen. That is the Cartesian product of the two sets, whose size is the product of their sizes, because each pair makes one choice from each factor. A power set asks a different question — which subset of one set is present — and answers n independent in-or-out choices, giving 2^n. Products grow by a factor's size; power sets double.
  • If enumerating label combinations is out, what does a filtering design keep instead?
    One set of documents per label, which is linear in the taxonomy, plus the algebra to combine them when a query arrives. A filter naming k labels then costs work proportional to those k sets rather than to the number of combinations. Storage grows as the taxonomy grows, not as its combinations grow.
  • How many subsets does a set of zero labels have?
    One: the empty set, since 2^0 = 1. This is not a degenerate curiosity — it is why 'no labels selected' is a legitimate member of the combination space rather than a missing case, and why a doubling argument that starts from a list containing the empty combination is the right starting point.

A wardrobe of n garments you may wear or leave off: each extra garment doubles the number of possible outfits. That is why even a modest wardrobe has more outfits than you could photograph one at a time.

saying these in an interview costs you the question

  • Says n labels give n possible label combinations.
  • Forgets the empty label set is one of the combinations.
  • Plans one precomputed cache entry per possible label combination.
  • Confuses the number of subsets with the number of label pairs.
  • Calls 2^n growth manageable because n is only twenty.
  • Believes bigger hardware moves the doubling wall meaningfully.