Pattern Recognition Drill
Medium 2-D Dynamic Programming
The Problem
Given nums and a target, assign + or - to each number to reach target. Count the number of ways.
What approach would you use?
Think about it before scrolling down.
Transform to subset sum: find subsets summing to (total+target)/2. Classic 0/1 knapsack. O(n * sum).
Recursive with memo on (index, current_sum). O(n * sum) but larger constant.
Common Trap
If (total + target) is odd or target > total, answer is 0. The math transformation is the key insight.