LeetCode 494. Target Sum

[Woodyiiiiiii]

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:

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.

---

这题我一开始就按照Coin Change 2的DP的思路，设置一个二维数组，dp[i][j]表示nums[i]下和为j的可能结果个数：

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int n = nums.length;
        int sum = 0;
        for (int num : nums)
            sum += num;
        if (S > sum || S < -sum) return 0;
        int[][] dp = new int[n + 1][2 * sum + 1];
        if (nums[0] != 0) dp[1][nums[0] + sum] = dp[1][-nums[0] + sum] = 1;
        else dp[1][sum] = 2;
        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j <= 2 * sum; ++j) {
                if (j - nums[i - 1] >= 0 && j + nums[i - 1] <= 2 * sum)
                    dp[i][j] = dp[i - 1][j - nums[i - 1]] + dp[i - 1][j + nums[i - 1]];
                else if (j - nums[i - 1] >= 0)
                    dp[i][j] = dp[i - 1][j - nums[i - 1]];
                else if (j + nums[i - 1] <= 2 * sum)
                    dp[i][j] = dp[i - 1][j + nums[i - 1]];
            }
        }
        return dp[n][S + sum];
    }
}

稍微不同的是，因为会出现负数，所以dp数组的列大小应该是所有数字绝对值之和的两倍，并且初始时要考虑0的情况。

当然，动态规划是暴力递归的优化，我们也可以考虑递归：

class Solution {
    private int sumWays = 0;
    public int findTargetSumWays(int[] nums, int S) {
        recursive(nums, 0, 0, S);
        return sumWays;
    }
    public void recursive(int[] nums, int level, int preSum, int S) {
        if (level >= nums.length) {
            if (preSum == S) ++sumWays;
            return;
        }
        recursive(nums, level + 1, preSum + nums[level], S);
        recursive(nums, level + 1, preSum - nums[level], S);
    }
}

---

参考资料：

• https://leetcode.com/problems/target-sum/
• [LeetCode] 494. Target Sum grandyang/leetcode#494