494. Target Sum

494. Target Sumopen in new window

🟠 🔖 数组 动态规划 回溯 🔗 LeetCodeopen in new window

题目

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);
};

494. Target Sum

# 494. Target Sumopen in new window

# 题目

# 题目大意

# 解题思路

# 思路一：回溯

# 思路二：动态规划 - 递归

# 思路三：动态规划 - 背包

# 代码

# 相关题目