Target Sum

Put a + or - sign in front of every number so that the resulting expression equals target. In how many ways can you do it? (Signs at different positions count as different ways, even when the numbers are equal.)

Input:

• line 1: n target
• line 2: n non-negative integers

Output: the number of ways.

Constraints: 1 ≤ n ≤ 20, 0 ≤ a[i] ≤ 1000, sum of a ≤ 1000, −1000 ≤ target ≤ 1000.

Think about it: trying all 2ⁿ sign patterns is about a million for n = 20 — fine here, but a DP over reachable sums (count[sum]) is far faster. Neat reduction: if P is the set with +, then sum(P) = (total + target) / 2 — a subset-count knapsack.