Enumerate every subset of a set of positions

Question

Given a set of distinct positions, produce every subset (the power set), including the empty set and the full set. For a scenario sweep you might want to price every possible sub-portfolio.

items = ["A", "B"]
-> [[], ["A"], ["A", "B"], ["B"]]

Return all 2^n subsets. The order of subsets does not matter, but each should appear exactly once.

Accepted Answer

Use backtracking with a start index so each element is only ever considered after the ones before it, that prevents generating the same subset in a different order. At every recursive call, record the current partial subset (it is a valid subset on its own), then try adding each remaining element, recurse, and undo. Tracing ["A", "B"]: we record [], then add A and record ["A"], then add B for ["A","B"], backtrack, and finally ["B"], four subsets. Time O(n 2^n) to build and copy all subsets, space O(n) for recursion depth (plus the output). Edge cases: an empty input yields exactly [[]]; dupli…

Enumerate every subset of a set of positions

Your answer

More Coding questions