Target Sum

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.

Solution

一開始自己思考這題是想到用 DFS 解，但實際寫的過程中反而把它複雜化，基本上就只是判斷 is valid 後，用兩個 recursion 去解就好。有個地方可以特別注意，就是 result 必須宣告為 global。在 Java 裡，如果你是傳一個 primitive type 進去 function，不論怎麼改，都不會影響上一層的值。

    int result = 0;

    public int findTargetSumWays(int[] nums, int S) {
        if (nums == null || nums.length == 0) return result;
        helper(nums, S, 0, 0);
        return result;
    }

    public void helper(int[] nums, int target, int pos, long eval){
        if (pos == nums.length) {
            if (target == eval) result++;
            return;
        }
        helper(nums, target, pos + 1, eval + nums[pos]);
        helper(nums, target, pos + 1, eval - nums[pos]);
    }

再往深一點想，可以發現這題能夠用 DP 來解。用 2D or 1D DP 其實概念都是一樣的，在每次的 iteration，都可以基於上一次的 sum 再去 +nums[i] or -nums[i]。特別注意在 1D DP 時，跑完這一輪要把 dp array 更新，因為每一輪都只基於上一輪

public int findTargetSumWays(int[] nums, int S) {
        if (nums.length == 0 || nums == null) {
            return 0;
        }

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if (S > sum || S < -sum) {
            return 0;
        }

        int[] dp = new int[2 * sum + 1];
        dp[sum + nums[0]] = 1;
        dp[sum - nums[0]] += 1;
        for (int i = 1; i < nums.length; i++) {
            int[] next = new int[2 * sum + 1];
            for (int j = -sum; j <= sum; j++) {
                if (dp[j + sum] > 0) {
                    next[j + sum + nums[i]] += dp[j + sum];
                    next[j + sum - nums[i]] += dp[j + sum];
                }
            }

            dp = next;
        }
        return dp[S + sum];
    }