Subsets — How the Pattern Works
The Subsets (Combinatorial Tree Enumeration) pattern constructs all valid subsets, permutations, Cartesian combinations, or rule-constrained sequences by modeling sequential item or position choices as levels of a decision tree. Whether expanded breadth-first (iteratively cascading partial results level by level) or depth-first via backtracking, each root-to-node path encodes a unique choice vector so every valid output is built once without post-hoc set deduplication. Early constraint pruning and duplicate-control invariants cut invalid or redundant subtrees immediately, reducing brute-force generate-and-filter work (such as O(n * n^n) slot trials or O(n * 4^n) unfiltered bracket strings) to complexity proportional to the valid output set.
- The prompt asks to list all subsets, combinations, permutations, or valid arrangements—or to count distinct sequences—rather than finding a single extremum.
- Input dimensions are small (typically n <= 15–20 for subsets/combinations or n <= 8–10 for permutations), signaling exponential O(2^n) or factorial O(n!) output sizes.
- Solutions decompose into one discrete choice per item or position: include/exclude, character case toggle, keypad letter mapping, or gap insertion.
- The input contains duplicate elements while outputs must be unique, calling for sorted last-layer cascading or frequency-counter backtracking.
- Appending directly to result while iterating over result without slicing or staging into a temporary grown list, causing an infinite loop as newly added subsets are re-extended in the same pass.
- Forgetting to sort nums before checking nums[i] == nums[i - 1] in duplicate-subset enumeration, or branching per duplicate index rather than per unique value in tile/permutation counting.
- Returning [""] instead of [] on empty input when problems like Letter Combinations of a Phone Number define zero positions as yielding zero combinations.
- Pruning branches with total + x > k when the input can contain zero or negative integers; monotonic upper-bound sum pruning requires strictly positive (or non-negative) remaining elements.
def subsets_cascading(nums):
result = [[]]
for x in nums:
grown = [curr + [x] for curr in result]
result += grown
return resultdef subsets_with_dup(nums):
nums = sorted(nums)
result, start_new = [[]], 0
for i, x in enumerate(nums):
start = start_new if (i > 0 and x == nums[i - 1]) else 0
start_new = len(result)
for s in result[start:start_new]:
result.append(s + [x])
return resultdef pruned_backtrack(n):
result = []
def grow(state, opened, closed):
if len(state) == 2 * n:
result.append(state)
return
if opened < n:
grow(state + "(", opened + 1, closed)
if closed < opened:
grow(state + ")", opened, closed + 1)
grow("", 0, 0)
return result