494. 目标和

🟠   🔖  数组 动态规划 回溯  🔗 力扣 LeetCode

题目

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 3

Output: 5

Explanation: There are 5 ways to assign symbols to make the sum of nums be target 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

Example 2:

Input: nums = [1], target = 1

Output: 1

Constraints:

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

题目大意

给你一个非负整数数组 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);
};

相关题目

题号	标题	题解	标签	难度
282	给表达式添加运算符		数学 字符串 回溯
2787	将一个数字表示成幂的和的方案数		动态规划