Leetcode - 494. Target Sum

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

---