代码随想录 Leetcode494. 目标和

题目：

---

代码(首刷看解析 2024年2月26日）

        思路：根据题意，设两个背包，packageA存放前面是"+"的数字之和，packageB存放前面是“-”的数字之和

则sum = packageA + packageB;

    target = packageA - packageB;

 则根据以上算式可得packageA = (sum + target)/2;

因为sum和target根据题目都已知，则问题变成求可以放哪些数使得和 == packageA--即动态规划01背包问题

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int& num :nums) {sum += num;}if (sum < abs(target)) return 0; int tmp = sum + target;if (tmp % 2 == 1) return 0;int x = tmp / 2;vector<int> dp(x + 1, 0);dp[0] = 1;for (int i = 0; i < nums.size(); ++i) {for (int j = x; j >= nums[i]; --j) {dp[j] += dp[j - nums[i]];}}return dp[x];}
};