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
