[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)，代码如下：

	class Solution {
	public:
	int findTargetSumWays(vector<int>& nums, int S) {
	int sum = 0;
	for(auto& num : nums)
	sum += num;
	int diff = sum - S;
	if(diff < 0 || diff % 2)return 0;
	return knapsack(nums, diff / 2);
	}
	private:
	int knapsack(vector<int>& nums, int target)
	{
	int len = nums.size();
	vector<int> dp(target + 1, 0);
	dp[0] = 1;
	for(int i = 0; i < len; ++i)
	{
	int num = nums[i];
	for(int j = target; j >= num; --j)
	{
	dp[j] += dp[j - num];
	}
	}
	return dp[target];
	}
	};

view raw Target Sum.cpp hosted with ❤ by GitHub