Loading...
Loading...
Loading...
A list has N non-negative numbers. Put a plus or a minus sign in front of every number. Count the sign choices where the total equals G. Choices with different signs on different positions are different, even when the numbers are equal.
Example 1
Input
5 3 1 1 1 1 1
Output
5
Choose which one of the five gets a minus.
Example 2
Input
1 2 1
Output
0
Try the problem first. Open one hint at a time.
Numbers with a plus form a group P and numbers with a minus form a group M. The total is sum(P) - sum(M), and sum(P) + sum(M) is the full total.
That means sum(P) must equal (total + G) / 2. Count subsets with that sum, and handle an impossible target first.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor