Subsets II
WHAT IT SAYS
Return all possible subsets of an array that may contain duplicate values, with no duplicate subsets in the output.
WHAT IT'S REALLY ASKING
"If the array holds three 2s, your subset cannot tell you WHICH 2s it took — only how many. So stop choosing elements and start choosing counts: for each distinct value, the only decision is a number between zero and its multiplicity."
All 2^n masks, then a hash set
O(2^n * n) time, plus a set holding every cloneEnumerate every bitmask over the n positions, build the subset each mask names, sort it, serialise it, and dump it into a set so identical subsets merge.
WHERE THE WORK IS WASTED — Point at the exact collapse. If a value has k copies, then 2^k different masks — every way of choosing WHICH copies — name only k+1 distinct outcomes, because the copies are indistinguishable. So for an array of five identical numbers, 32 masks produce 6 answers, and you sort and hash 26 pieces of garbage to find that out. The true answer count is the product of (multiplicity + 1) across the distinct values, and the gap between that and 2^n is precisely the volume of trash you are generating on purpose.
The output sees how many you took, not which.
A subset of a multiset is fully described by one number per distinct value: how many copies did you take. Nothing else survives into the answer. 'Which 2' is a distinction the output has no vocabulary for. So the real decision tree is not binary at all. For a value with k copies, the branch has k+1 children — take 0, take 1, ... take k — and every one of them leads to a genuinely different subset. Multiply across the distinct values and you get the exact answer count, which is also a promise: walk that tree and you will produce every subset exactly once, with no set, no sorting, no filtering. Sort the array and the copies of each value become a contiguous run, which is what makes 'how many did I take' expressible as an index. Then either formulation works, and they are the same statement: (a) At each level, iterate the count t from 0 to k, take the first t copies of the run, recurse past the whole run. The first t copies are the canonical representative of 'I took t of them'. (b) Recurse element by element with a start index, and skip a[j] whenever j is past start and a[j] equals a[j-1]. That skip is doing exactly the same job: it forbids the second copy from being chosen as a first pick at the same level, so 'take copy 2 and not copy 1' — a different mask, same subset — never gets built. One last thing that separates this from Combination Sum: a subset is recorded at EVERY node of the tree, not only at the leaves. There is no target to hit, so every partial path is itself an answer.
Sort, record at every node, skip equal siblings
O(2^n * n) worst case, but exactly product-of-(multiplicity+1) answers with zero duplicates generatedSort the array. Recurse with a start index, and push the current path into the output the moment you enter the call — every node is an answer. Then loop j from start: skip j when j is past start and a[j] equals a[j-1]; otherwise take a[j], recurse from j+1, and undo.
Choose Counts, Not Copies
YOU'LL SEE IT AGAIN WHEN
- The input is a multiset and equal items are interchangeable, so 'which copy' is a distinction the answer cannot express.
- The naive enumeration is 2^n but the true answer count is the product of (multiplicity + 1) — and that gap IS the duplicate flood.
- The output is produced at every node of the recursion rather than only at complete leaves — there is no target, so every partial path counts.