Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Reuse a choice without reordering it: The Target Combinations.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Combination sum matches the clues
- 2Keep this true after every move: path is nondecreasing and remaining equals target minus its sum
- 3Reach the result within output-sensitive exponential time
Rules and pressure
- Target cost: output-sensitive exponential time
- State rule: path is nondecreasing and remaining equals target minus its sum
Lesson 1 of 3
Live algorithm trace
Combination sum
Complete execution1 of 5
2
candidate
3
6
7
0
7
Begin with the entire target remaining.
1
search(start, remaining)2
if remaining is zero: record3
for each candidate from start4
stop when candidate exceeds remaining5
choose and recurse from same index6
undoremaining = 7path = []
Truth to preserve / Cost target
Truth to preserve
path is nondecreasing and remaining equals target minus its sum
Cost target
output-sensitive exponential time
A branch chooses candidates from a nondecreasing index onward. Reusing the same index permits unlimited copies, while never returning to earlier indices prevents permutation duplicates.
Your call · What should guide every step of this algorithm?