Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 494 Target Sum - Problem Statement

LeetCode 494

Given an array numsnums and a target, assign + or - to each number so they sum to target. Return the count of ways to do this. For example, with nums=[1,1,1,1,1]nums = [1, 1, 1, 1, 1] and target =3= 3, there are 55 ways. This looks like a different problem entirely. You're assigning signs, not selecting subsets.

But there's a clever transformation hiding here. Before reading the solution, try this: if you call the numbers with + signs "PP" and numbers with - signs "NN", what equations can you write?