494. Target Sum

494. Target Sum

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.

---------------------------

Solution #1, straightforward recursion
O(2^n)

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        return helper(nums, 0, S);
    }
    
    private int helper(int[] nums, int index, int sum) {
        if (index == nums.length && sum == 0) return 1;
        if (index >= nums.length) return 0;
        
        return helper(nums, index + 1, sum - nums[index]) 
            + helper(nums, index + 1, sum + nums[index]);
    }
}

Solution #2
Memoization
会发现此题有重复的子问题，DP可解：
+ 1 - 1 [11] 跟 - 1 + 1 [11], 括号内为重复
+ 1 + 2 - 3 [4 5 6] 跟 - 1 - 2 + 3 [4 5 6]

很难直接从递归就看出它的复杂度，因为取决于生成不同sum的个数。树的深度为nums的长度
class Solution {

    public int findTargetSumWays(int[] nums, int S) {
        return helper(nums, 0, S, new HashMap());
    }
    
    private int helper(int[] nums, int index, int sum, Map cache) {
        if (index == nums.length && sum == 0) return 1;
        if (index >= nums.length) return 0;
        
        String plusKey = index + "+" + sum;
        int plus = 0;
        if (cache.containsKey(plusKey)) {
            plus = cache.get(plusKey);
        } else {
            plus = helper(nums, index + 1, sum - nums[index], cache);    
            cache.put(plusKey, plus);
        }
        
        String minusKey = index + "-" + sum;
        int minus = 0;
        if (cache.containsKey(minusKey)) {
            minus = cache.get(minusKey);
        } else {
            minus = helper(nums, index + 1, sum + nums[index], cache);   
            cache.put(minusKey, minus);
        }        
        
        return plus + minus;
    }
}

Solution #3,遍历DP，跟上面Memoization一样，每一个小问题都可以用（index, sum）的组合来表示
O(n * m) 时间，n为nums的changdu，m为最长的sums的可能性

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int n = nums.length;
        Map sums = new HashMap<>();
        Map newSums = new HashMap<>();
        sums.put(S, 1);
        
        for (int i = n - 1; i >= 0; i--) {
            int num = nums[i];
            
            for (Map.Entry pair : sums.entrySet()) {
                int sum1 = pair.getKey() - num;
                addToNewMap(newSums, sum1, pair.getValue());
                
                int sum2 = pair.getKey() + num;
                addToNewMap(newSums, sum2, pair.getValue());
            }
            
            Map tmp = sums;
            sums.clear();
            sums = newSums;
            newSums = tmp;
        }
        
        return sums.getOrDefault(0, 0);
    }
    
    private void addToNewMap(Map cur, int sum, int value) {
        if (!cur.containsKey(sum)) {
            cur.put(sum, 0);
        }
        cur.put(sum, value + cur.get(sum));
    }
}

其他：因为题目已经给定所有数的sum不会超过1000，所以有一种方法是开一个大小为1000(?或者2000 ＋ 1，因为要考虑0和负数)的数组，每次遍历一下就是了。
但是以上我的方法不会被1000所限制。

Update: 发现Solution #2-#3原来就是所谓的subset sum