Problem context and objectives
Mission briefing
Dungeon strategy engineer · A robot must cross a tiled dungeon
Store enough solved tile states to plan the complete route: The Signed Target.
A greedy step can trap the robot; recomputing every route is too expensive.
How you win
- 1Recognize when Target sum knapsack matches the clues
- 2Keep this true after every move: counts[sum] equals the number of sign choices for the processed prefix that produce sum
- 3Reach the result within O(n times number of reachable sums)
Rules and pressure
- Target cost: O(n times number of reachable sums)
- State rule: counts[sum] equals the number of sign choices for the processed prefix that produce sum
Lesson 1 of 3
Live algorithm trace
Target sum knapsack
Complete execution1 of 6
1
number
1
1
1
1
The empty prefix has one way to make zero.
1
counts = {0: 1}2
for each number3
create an empty next map4
for each reachable sum and count5
add count to sum + number and sum - number6
return count at targetcounts = 0:1target = 3
Truth to preserve / Cost target
Truth to preserve
counts[sum] equals the number of sign choices for the processed prefix that produce sum
Cost target
O(n times number of reachable sums)
After each number, every reachable sum branches into adding or subtracting that number. A map stores how many sign assignments reach each resulting sum.
Your call · What should guide every step of this algorithm?