LeetCode 494 - Target Sum

作者 QIFAN 日期 2017-01-29
LeetCode 494 - Target Sum

原题链接: 494. Target Sum


题干

给定一串 integer 数组 a ,和一个目标 S ,要求只使用“ + ”与“ - ”,返回能够用这些 integer 组成 S 的方式个数。不能重复使用数字。

思路

DFS

这个很像 DP ,假设之前符号全都是“ - ” ,逐个把“ - ”改成“ + ”,对于位置 i 的数,它的和 sum 等于上一个状态的和加上 2 * a[i] ,若 sum == S ,那就 count++ ;若 sum > S 那就不必考虑再在这个状态后添加加号的情况。

时间复杂度 $O(N^2)$ ,空间复杂度 $O(1)$ 。

这个方法慢的原因在于相同状态的重复计算。

让我想到这道题 Permutations With Duplicates

代码:

int count = 0;
public int findTargetSumWays(int[] nums, int S) {
if (nums == null || nums.length == 0) {
return 0;
}
int sum = 0;
for (int i: nums) {
sum -= i;
}
if (sum > S || -sum < S) {
return 0;
}
dp(S - sum, nums, 0, nums.length - 1);
return count;
}
private void dp(int diff, int[] nums, int lo, int hi) {
if (diff == 0) {
count++;
} else if (diff < 0 || lo > hi) {
return;
}
for (int i = lo; i <= hi; i++) {
int newdiff = diff - nums[i] * 2;
dp(newdiff, nums, i + 1, hi);
}
}

背包解法

讨论区有一个很厉害的解法,把这道题转成了背包问题,我也想到过这一块,但是没想出状态方程。
参考: https://discuss.leetcode.com/topic/76243/java-15-ms-c-3-ms-o-ns-iterative-dp-solution-using-subset-sum-with-explanation

它将题目简化为,将 nums 分成一个正数集合 P 与一个负数集合 N ,使 sum(P) - sum(N) = target。更厉害转化在下面:

sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
2 * sum(P) = target + sum(nums)
sum(P) = (target + sum(nums)) / 2

这就变成了在 nums 中找和为 (target + sum(nums)) / 2 的集合个数,这就是一个背包!
状态方程为 dp[sum] = dp[sum - nums[i]] + dp[nums[i]]

而且 (target + sum(nums)) 一定是偶数。

时间复杂度为 $O(NS)$ 。

代码:

public int findTargetSumWays(int[] nums, int s) {
int sum = 0;
for (int n : nums)
sum += n;
return sum < s || (s + sum) % 2 > 0 ? 0 : subsetSum(nums, (s + sum) >>> 1);
}
public int subsetSum(int[] nums, int s) {
int[] dp = new int[s + 1];
dp[0] = 1;
for (int n : nums)
for (int i = s; i >= n; i--)
dp[i] += dp[i - n];
return dp[s];
}