[dfs, dp] 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:
The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

DFS的思路首先想出来，顺利写出来：

    public int findTargetSumWays(int[] nums, int S) {
        return helper(nums, S, 0, 0, 0);
    }
    
    private int helper (int[] nums, int S, int index, int sum, int count) {
        if (index == nums.length) {
            if (sum == S) return count + 1;
            else return count;
        } 
        int count1 = helper(nums, S, index + 1, sum + nums[index], count);
        int count2 = helper(nums, S, index + 1, sum - nums[index], count);
        return count1 + count2;
    }

这种recusion其实都类似，一般都在helper函数里需要给index，记录当前看到哪个元素；原函数需要什么就return什么（需要count就return count，需要所有的排列组合就return list或者set之类的）。

但是，recusion很慢，写的时候也能感觉到，各种排列组合应该有很多重复的时候。

一般，dfs的问题想improve，可以考虑dp。只是这个问题直接从dfs的code改成dp，无从下手。

要及时抛弃已经有的dfs code，重新想思路。

新思路：题目转化找到一个subset都是positive，剩下的subset都是negative，使得 P – N == target. 已知 P + N == sum, 则 2P = target + sum, p = (target + sum) / 2。题目转化成找到一个subset，使其和等于(target + sum) / 2。这个新问题，用dp做。

    private int helper(int[] nums, int target) {
        int[] dp = new int[target + 1]; //存有几种组合可以达到当前目标(1...target)
        dp[0] = 1;
        for (int n : nums) {
            for (int i = target; i >= n; i--) { //倒着看
                dp[i] += dp[i - n]; //新来的数是n，现在只要可以达到i-n就可以达到i
            }
        }
        return dp[target];
    }

可以考虑dp解决这个新问题也是一个模版，而且是典型的dp模版。