494.目标和

目标和

给你一个非负整数数组 nums 和一个整数 target。向数组中的每个整数前添加 ‘+’ 或 ‘-‘，然后串联起所有整数。返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

解析

转化为背包问题：设正数和为 P，负数和为 N，则 P - N = target, P + N = sum，所以 P = (sum + target) / 2。

var findTargetSumWays = function (nums, target) {
  const sum = nums.reduce((a, b) => a + b, 0);
  if ((sum + target) % 2 !== 0 || sum < Math.abs(target)) return 0;
  const bag = (sum + target) / 2;
  const dp = new Array(bag + 1).fill(0);
  dp[0] = 1;
  for (const num of nums) {
    for (let j = bag; j >= num; j--) dp[j] += dp[j - num];
  }
  return dp[bag];
};