239. Target Sum with Signs
MediumDynamic ProgrammingCounting
Put a + or − before every number. Count the assignments whose total equals the target.
Input format
Line 1: n target Line 2: n non-negative integers
Output format
The number of ways.
Example 1
Input
5 3 1 1 1 1 1
Output
5
Example 2
Input
1 1 1
Output
1
Constraints
1 ≤ n ≤ 20 0 ≤ values ≤ 1000
Read input from standard input and print the answer to standard output. Your code is judged against 4 test cases, most of them hidden.
Loading the MyLoginn IDE…