[Leetcode 494] Target Sum

作者 Shilei Tian 日期 2017-02-10
[Leetcode 494] Target Sum

题目要求

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation:

-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

There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

  1. The length of the given array is positive and will not exceed 20.
  2. The sum of elements in the given array will not exceed 1000.
  3. Your output answer is guaranteed to be fitted in a 32-bit integer.

解题思路

根据题目的要求,我们很容易就能写出一个暴力(深搜)的解法来,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
helper(nums, 0, S);
return count;
}

private:
void helper(const vector<int>& nums, const int cur, int target) {
if (cur == nums.size()) {
if (target == 0) {
++count;
}
return;
}
helper(nums, cur + 1, target + nums[cur]);
helper(nums, cur + 1, target - nums[cur]);
}
int count = 0;
};

在 Leetcode 上面的运行时间是 525ms,能够击败 38.63% 的人,看起来结果不算很好。不过这道题是非常典型的动态规划问题,所以我们考虑使用动态规划来解。

题目要我们给序列里面的每个元素分配一个符号,使得最后的和等于目标值,那实际上不就变成我们从给定序列中找两个子集 PN,使得 sum(P) - sum(N) = SP + N = nums 了吗?化简一点就是我们需要找到一个集合 P,使得 sum(P) = S - sum(nums - P)。那我们是不是每次需要求出 sum(P)sum(nums - P) 呢?其实不然,我们考虑化简 sum(P) - sum(N) = S

sum(P) - sum(N) = S

sum(P) + sum(N) + sum(P) - sum(N) = S + sum(P) + sum(N)

2 * sum(P) = S + sum(nums)

sum(P) = (S + sum(nums)) / 2

也就是说,我们只需要找到一个集合 P,使得 sum(P) 等于 (S + sum(nums)) / 2 即可,问题立马变得清晰了起来,这样我们就可以用非常基础的动态规划来解决了,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum < S || ((S + sum) & 0x1) == 1) {
return 0;
}
int target = (S + sum) >> 1;
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (auto num : nums) {
for (int i = target; i >= num; --i) {
dp[i] += dp[i - num];
}
}
return dp[target];
}
};

运行时间仅仅 3ms,整整少了两个数量级!