494. Target Sum

二刷 06/2022

Version #1 1D DP

不知道为啥intuitively就是觉得特别简单，完全没有想到recursion上面去

思路就是until index i我们有一个map维护之前全部的sum可能性

然后当前有可能+nums[i]/-nums[i],再更新map

Time O(N * t) -> t is the sum of numbers

Space O(t)

Runtime: 64 ms, faster than 55.34% of Java online submissions for Target Sum.

Memory Usage: 42.1 MB, less than 60.80% of Java online submissions for Target Sum.

class Solution {

    public int findTargetSumWays(int[] nums, int target) {

        if (nums == null || nums.length == 0) {

            return 0;

        }

        // key-value of expression until current number

        // value-count of that value

        Map<Integer, Integer> map = new HashMap<>();

        map.put(0, 1);

        for (int i = 0; i < nums.length; i++) {

            Map<Integer, Integer> tempMap = new HashMap<>();

            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {

                int val = entry.getKey() + nums[i];

                tempMap.put(val, tempMap.getOrDefault(val, 0) + entry.getValue());

                val = entry.getKey() - nums[i];

                tempMap.put(val, tempMap.getOrDefault(val, 0) + entry.getValue());

            }

            map = tempMap;

        }

        return map.getOrDefault(target, 0);

    }

}

一刷
0/1 Knapsack Problem

83.05 %
class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        // 2 dimension of states
        // dp[i][j] -> nums[0, i], with sum of j
        // since sum can be negative, we need to add offset to all sums
        int len = nums.length;
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        // partition nums into to sets -> positive set P and negative set N
        // sum(P) - sum(N) = target
        // sum(P) + sum(N) = total
        // 2 sum(P) = S + total
        // sum(P) = (S + total) / 2;
        int target = total + S;
        if (total < S || target % 2 != 0) return 0;
        target /= 2;
        // find a subset sum equals to S + total
        // dp[i][j] -> pick any number from [0, i) -> sum to j
        int[][] dp = new int[len + 1][target + 1];
        for (int i = 0; i <= len; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= len; i++) {
            for (int s = 0; s <= target; s++) {
                // if we don't pick current nums[i - 1]
                dp[i][s] = dp[i - 1][s];
                if (s >= nums[i - 1]) {
                    dp[i][s] += dp[i - 1][s - nums[i - 1]];
                }
            }
        }
        return dp[len][target];
    }
}