Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Skip equal siblings at one decision depth: The Unique Power Set.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Subsets with duplicates matches the clues
- 2Keep this true after every move: no decision depth starts two branches with the same value
- 3Reach the result within O(number of unique subsets times n)
Rules and pressure
- Target cost: O(number of unique subsets times n)
- State rule: no decision depth starts two branches with the same value
Lesson 1 of 3
Live algorithm trace
Subsets with duplicates
Complete execution1 of 5
1
choice
2
2
0
1
2
Sort and record the empty subset.
1
sort values2
record current path3
for index from start4
if index > start and equals previous: skip5
choose, recurse at index + 16
undo and return unique pathssorted = [1,2,2]path = []
Truth to preserve / Cost target
Truth to preserve
no decision depth starts two branches with the same value
Cost target
O(number of unique subsets times n)
Sort equal values together. At one recursive depth, only the first equal sibling may start a branch, while deeper recursion may still take another copy.
Your call · What should guide every step of this algorithm?