解题思路:1.因为每个数字都有正负两种选择,所以可以采用回溯算法。(会超时)
2.分成两个集合,分别为正数集合(left)和负数(right)集合。
left + right = Sum ---> right = Sum - left
left - right = target
联立得到:
left = (target + Sum) / 2
如果不能整除,则凑不出target
dp数组含义:装满容量为j的背包的方法
递推公式:d[j] = d[j] + d[j-numbers[i]](放i和不放i)
初始化:dp[0] = 1(装满容量为0的背包有1种方法),其余非0下标初始化为0
代码实现: