LeetCode 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];
}

题干
思路
1. DFS
2. 背包解法

LeetCode 494 - Target Sum

题干

思路

DFS

背包解法

FEATURED TAGS

FRIENDS