原题链接: 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]; }
|