494 Target Sum

494. Target Sum

1. Question

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.

2. Implementation

(1) DFS

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int[] res = new int[1];
        findTargetSum(0, 0, S, nums, res);
        return res[0];
    }

    public void findTargetSum(int index, int curSum, int target, int[] nums, int[] res) {
        if (index == nums.length) {
            if (curSum == target) {
                ++res[0];
            }
            return;
        }

        findTargetSum(index + 1, curSum + nums[index], target, nums, res);
        findTargetSum(index + 1, curSum - nums[index], target, nums, res);
    }
}

(2) DP

思路: 假设nums中有i个元素是正号， n - i个元素用负号，则Sum(i) + Sum(n - i) = S, 显然Sum(n) = Sum(i) - Sum(n - i), 则Sum(i) + Sum(n - i) = S可转变为Sum(i) + Sum(n - i) + Sum(i) - Sum(n - i) = S + Sum(i) - Sum(n - i) =>

2 * Sum(i) = S + Sum(n).这样我们的问题就转变为了求Subset sum Sum(i)，这就将问题转化为了 0/1背包问题。

dp[i][j]表示用前i个item，组成target sum为j的所有方式。dp[0][0]初始化为1，因为对于空集来说，如果没有任何item的话，得到空集的方式是一种。

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {        
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if (sum < S || (sum + S) % 2 != 0) {
            return 0;
        }

        int n = nums.length;
        int target = (sum + S) / 2;
        int[][] dp = new int[n + 1][target + 1];
        // 对于空集，有一种方法可以得到它，就是什么元素都不选
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= target; j++) {
                if (nums[i - 1] <= j) {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                }
                else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][target];
    }
}

3. Time & Space Complexity

DFS: 时间复杂度O(2^n)， 枚举所有可能的组合，每个元素要不前面用正好，要不用负号，总共2^n个选择, 空间复杂度O(n) 递归的深度是n

DP: 时间复杂度O(n * target), 空间复杂度O(n * target)