You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 
-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 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

  1. The length of the given array is positive and will not exceed 20.
  2. The sum of elements in the given array will not exceed 1000.
  3. Your output answer is guaranteed to be fitted in a 32-bit integer.

思路

利用动态规划解决问题。

分析例子：有5个数，转化成前四个数与第五个数之和为3；则转化成前三个数与第四个数之和为2或者4；则转化为前两个数与第三个数之和为1,3,3或5。

我们此时可以考虑用哈希表存储结果。直到数组遍历完全，问题可以得到解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution(object):    
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        stats = {}
        if(len(nums)):
            if (len(nums) == 1):
                if (nums[0] == S or nums[0] == -S):
                    if (nums[0]):
                        return 1
                    else:
                        return 2
                else:
                    return 0
            elif (len(nums) > 1):
                if (nums[0]):
                    stats[S-nums[0]] = 1
                    stats[S+nums[0]] = 1
                else:
                    stats[S] = 2
                tmp = {}
                for i in nums[1:]:
                    for j in stats.keys():
                        if (tmp.has_key(j-i)):
                            tmp[j-i] += stats[j]
                        else:
                            tmp[j-i] = stats[j]
                        
                        if (tmp.has_key(j+i)):
                            tmp[j+i] += stats[j]
                        else:
                            tmp[j+i] = stats[j]
                    stats = tmp
                    tmp = {}
                if (stats.has_key(0)):
                    return stats[0]
                else:
                    return 0

一开始我还是想用常规方式解决问题。

先求和，如果需要改变数的符号，就是要减去这个数两次。如果可以找到所有元素之和，与待求元素之差的话，应该可以解决问题。

实际上，如果遇到带0的元素，就会有困难，可能会陷入死循环当中。

而且，还会出现重复累加的情况，选取的应为组合数；重复累加就会变成排列数，最后的结果总是会大一些。

在做题的时候，我还不会利用DFS解决组合数的问题。这也是利用常规方法解决问题失败的原因之一。

测试用例：

1
2
[9,7,0,3,9,8,6,5,7,6]
2

参考资料：

http://blog.csdn.net/woshioosm/article/details/7438834