Enumerating every choice
Many problems require all subsets, all permutations, or all combinations of a set. The subsets pattern builds these systematically using a breadth first style growth that doubles the result set with each new element, avoiding tangled recursion.
Grow by cloning
Start with a result list containing a single empty set. Then process the input one element at a time.
- Take a snapshot of all subsets gathered so far.
- For each subset in that snapshot, make a copy and add the current element.
- Append every new subset to the result list.
After one element the result has two subsets, after two it has four, and so on, exactly doubling because every existing subset spawns one new variant that includes the latest element.
Handling duplicates and order
When the input has repeats, sort it first and only extend subsets created in the previous round to avoid generating the same subset twice. The same cloning idea adapts to permutations by inserting the new element at every position of each existing arrangement.
Key idea
Generate all subsets by copying every subset found so far and adding the next element, doubling the collection at each step without deep recursion.