102. 加减的目标值
102. 加减的目标值
题目
给定一个正整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入： nums = [1,1,1,1,1], target = 3
输出： 5
解释： 一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：
输入： nums = [1], target = 1
输出： 1
提示：
1 <= nums.length <= 201 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
注意
本题与 LeetCode 第 494 题 相同。
题目大意
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
解题思路
思路一：回溯
任何算法的核心都是穷举，回溯算法就是一个暴力穷举算法，在 《3.4 回溯算法》 中讲了回溯算法框架：
function backtrack(路径, 选择列表) {
if (满足结束条件) {
result.add(路径);
return;
}
for (选择 in 选择列表) {
做选择;
backtrack(路径, 选择列表);
撤销选择;
}
}
- 根据模版框架，可以使用回溯算法，尝试每一种可能的组合；
- 递归函数
backtrack中，对于当前数字，分别考虑添加正负号，然后递归到下一层； - 如果遍历完所有数字后，目标值为 0，则说明找到一种组合；
复杂度分析
- 时间复杂度：
O(2^n)，其中n是数组nums的长度，每个数字都有两种选择，加或者减。重复计算较多，非常低效。 - 空间复杂度：
O(n)，递归栈的深度。
思路二：动态规划 - 递归
动态规划之所以比暴力算法快，是因为动态规划技巧消除了重叠子问题。使用动态规划和递归结合的思路，使用哈希表 dp 存储中间结果，可以避免重复计算。
递归函数 helper 中，对于每个数字，分别考虑添加正负号，然后递归到下一层。
复杂度分析
- 时间复杂度：
O(n * target)，其中n是数组nums的长度，每个数字都有两种选择，加或者减。 - 空间复杂度：
O(n * target)，存储中间结果的哈希表。
思路三：动态规划 - 背包
这个问题还可以转化为一个子集划分问题，而子集划分问题又是一个典型的背包问题。
首先，如果把 nums 划分成两个子集 A 和 B，分别代表分配 + 的数和分配 - 的数，那么他们和 target 存在如下关系：
sum(A) - sum(B) = target
sum(A) = target + sum(B)
sum(A) + sum(A) = target + sum(B) + sum(A)
2 * sum(A) = target + sum(nums)
综上，可以推出 sum(A) = (target + sum(nums)) / 2，也就把原问题转化成了一个典型的背包问题：nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2？
- 使用动态规划数组
dp[i][j]表示在前i个物品中选择，容量为j的背包有多少种装法。 - 根据状态转移方程
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]，实现动态规划。 - 又由于
dp[i][j]只和dp[i - 1][...]有关，所以可以对动态规划数组进行状态压缩，仅使用一位数组储存当前行的计算结果，唯一注意的是，j需要从后往前遍历。- 因为二维压缩到一维的根本原理是，
dp[j]和dp[j-nums[i-1]]还没被新结果覆盖的时候，相当于二维dp中的dp[i-1][j]和dp[i-1][j-nums[i-1]]。 - 那么就要做到：在计算新的
dp[j]的时候，dp[j]和dp[j-nums[i-1]]还是上一轮外层for循环的结果。 - 如果你从前往后遍历一维
dp数组，dp[j]显然是没问题的，但是dp[j-nums[i-1]]已经不是上一轮外层for循环的结果了，这里就会使用错误的状态，当然得不到正确的答案。
- 因为二维压缩到一维的根本原理是，
代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function (nums, target) {
let res = 0;
if (nums.length == 0) return res;
const backtrack = (i, rest) => {
// base case
if (i == nums.length) {
// 说明恰好凑出 target
if (rest == 0) {
res++;
}
return;
}
// 给 nums[i] 选择 - 号
rest -= nums[i];
backtrack(i + 1, rest);
rest += nums[i];
// 给 nums[i] 选择 + 号
rest += nums[i];
backtrack(i + 1, rest);
rest -= nums[i];
};
backtrack(0, target);
return res;
};
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function (nums, target) {
if (nums.length == 0) return 0;
const dp = new Map();
const helper = (i, rest) => {
// base case
if (i == nums.length) {
if (rest == 0) return 1;
return 0;
}
// 转成字符串作为哈希表的键
const key = i + '_' + rest;
// 避免重复计算
if (!dp.has(key)) {
// 记入哈希表
dp.set(
key,
helper(i + 1, rest - nums[i]) + helper(i + 1, rest + nums[i]) // 还是穷举
);
}
return dp.get(key);
};
return helper(0, target);
};
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function (nums, target) {
const sum = nums.reduce((num, acc) => num + acc, 0);
if (sum < target || -sum > target || (sum + target) % 2 == 1) return 0;
const subset = (nums, sum) => {
const dp = new Array(sum + 1).fill(0);
dp[0] = 1;
for (let num of nums) {
for (let j = sum; j >= 0; j--) {
if (j >= num) {
dp[j] = dp[j - num] + dp[j];
}
}
}
return dp[sum];
};
return subset(nums, (sum + target) / 2);
};