Example 1:
Input:nums is [1, 1, 1, 1, 1], S is 3.Output:5Explanation:-1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3There are 5 ways to assign symbols to make the sum of nums be target 3.
simple solution:
(DFS)
there are two trees in the problem, one is the tree start with positive, another oen is the tree start with negative tree.
for example
[1,1,1]
------------------
T1(left for sub , right for add)
1
0 2
-1 1 1 3
T2
-1
-2 0
-3 -1 -1 1
then we add the total of the result of these two trees
WHILE, python will have time limit exceed problem .. you know , python....
this is the DP solution, which is extremely fast
https://discuss.leetcode.com/topic/76205/python-dp/7
