[LeetCode]Target Sum

这道题要我们从数组中找到一部分数，将其变为负数，使数组的和为target，总共有多少种方法。那么假设数组的和为sum，我们要找的那部分数和为x，我们可以得到sum - 2 * x = target。也就是说我们要找到一部分数使其和为(sum - target) / 2，那么这就是knapsack problem的变形，和Coin Change II是一样的。用DP[i][j]来表示前i + 1个物品填满容量为j的背包的方法数，c[i]表示第i + 1个物品的体积，递推公式为：

• DP[i][j] = DP[i - 1][j] + DP[i][j - c[i]]

假设背包体积为V，物品数为n，时间复杂度O(V * n)，空间复杂度O(V)，代码如下：