December 07, 2019

494. Target Sum

Sol 1. 2D DP

dp[i][j]: # of ways to sum up to j up to the ith index
dp is faster than dfs because S « O(2^n)

Transition 1: Pull (Scan j for dp[i])
dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]
(前i-1个数字能组成j-nums[i],第i个数字减nums[i], 前i-1个数字能组成j+nums[i]，第i个数字加nums[i])

Transition 2: Push (Scan j for dp[i - 1])
dp[i][j - num[i]] += dp[i - 1][j]
dp[i][j + num[i]] += dp[i - 1][j]

Time = O(n * sum), space = O(n * sum)

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (Math.abs(S) > sum) {
            return 0;
        }
        int[][] dp = new int[nums.length][2*sum + 1];
        dp[0][nums[0] + sum] += 1;
        dp[0][-nums[0] + sum] += 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = -sum; j <= sum; j++) {
                if (dp[i - 1][j + sum] > 0) {
                    dp[i][j + sum + nums[i]] += dp[i - 1][j + sum];
                    dp[i][j + sum - nums[i]] += dp[i - 1][j + sum];
                }
            }
        }
        return dp[dp.length - 1][S + sum];
    }
    
}

Sol 2. 1D DP

由于i+1的值和i有关，可以使用滚动数组降维。

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (Math.abs(S) > sum) {
            return 0;
        }
        int[] dp = new int[2*sum + 1];
        dp[nums[0] + sum] += 1;
        dp[-nums[0] + sum] += 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 + nums[i] + sum] += dp[j + sum];
                    next[j - nums[i] + sum] += dp[j + sum];
                }
            }
            dp = next;
        }
        return dp[S + sum];
    }
    
}

Sol 3. 2D DP (0/1 Knapsack)

Let P denotes a set of nums have a + sign in front of it
Let N denotes a set of nums have a - sign in front of it

sum(P) - sum(N) = target
sum(P) + sum(P) = target + sum(P) + sum(N)
2 * sum(P) = target + sum(a)

sum(P) = (target + sum(a))/2 ->转化成 0/1背包: 转化成给一个数组，从这个数组中选出若干的数字使他们的和为p，有多少种选法。How many ways to find some numbers out of an array whose sum is p?

dp[i][j]: whether we can use the first i elements to sum up to j

Transition 1: Scan j for dp[i - 1]: push
dp[i] = dp[i - 1]
dp[i][j + a_i] += dp[i - 1][j]

Transition 2: Scan j for dp[i]: pull
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a_i]
scan j in reverse order
dp[j] += dp[j - num_i], one array, j is decreasing will not affect this iteration

TODO

Sol 4. Backtracking (DFS)

这个做法类似 282. Expression Add Operators.

思路:
尝试所有放置正负号

Add: 对第i个数字添加正号(nums[i])，从i+1开始后面所有数字的结果是 S-nums[i]
Minus: 对第i个数字添加负号(-nums[i])，从i+1开始后面所有数字的结果是 S+nums[i]
(这样可以让第i个数字和从i+1开始后面所有数字的结果相加等于S.)
递归终止条件：为所有数字添加了正号或负号。当所有数字都处理完之后，S为0说明找到了一个方法返回1, 否则说明没有找到返回0。
(因为每次找到一个数字(添加正负号)结果都从S里面扣除了，如果所有数字处理完S为，0说明我们已经找到target)

Time = O(2^n): 数组长度为n，每个数字有2种选择 There are n steps if there are n numbers; There are 2 options at each step space = O(n): 数组长度为n，递归深度也为n

class Solution {
    private int res;
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (Math.abs(S) > sum) {
            return 0;
        }
        
        dfs(nums, 0, S);
        return res;
    }
    
    private void dfs(int[] nums, int index, int S) {
        if (nums.length == index) { // 递归终止条件：为所有数字添加了正号或负号
            if (S == 0) { // 当所有数字都处理完之后，S为0说明找到了一个方法
                res ++;
            }
            return;
        }
        dfs(nums, index + 1, S + nums[index]); // 为第i个数字添加负号
        dfs(nums, index + 1, S - nums[index]); // 为第i个数字添加正号
        // dfs index+1 代表下一步要去处理下一个数字
    }
}

另一种写法：

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (Math.abs(S) > sum) {
            return 0;
        }
        return dfs(nums, 0, S);
    }
    
    private int dfs(int[] nums, int index, int S) {

        if (nums.length == index) { // 递归终止条件：为所有数字添加了正号或负号
            return S == 0 ? 1 : 0; // 当所有数字都处理完之后，S为0说明找到了一个方法
        }
        int add = dfs(nums, index + 1, S + nums[index]); // 为第i个数字添加负号
        int minus = dfs(nums, index + 1, S - nums[index]); // 为第i个数字添加正号
        // dfs index+1 代表下一步要去处理下一个数字
        return add + minus;
    }
}

Sol 5. Backtracking (DFS) Optimized: Pruning

剪枝: 所有数字添加加号得到的结果是最大的，反之亦然, Math.abs(S) <= sum

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

        if (nums.length == index) { // 递归终止条件：为所有数字添加了正号或负号
            return S == 0 ? 1 : 0; // 当所有数字都处理完之后，S为0说明找到了一个方法
        }
        if (Math.abs(S) > sum) { // 剪枝, 减少不必要的递归路径
            return 0;
        }
        int add = dfs(nums, index + 1, S + nums[index], sum - nums[index]); // 为第i个数字添加负号
        int minus = dfs(nums, index + 1, S - nums[index], sum - nums[index]); // 为第i个数字添加正号
        // dfs index+1 代表下一步要去处理下一个数字
        return add + minus;
    }
}

Sol 6. Backtracking (DFS) Optimized：Memoization

Duplicate subproblems: to count the ways to sum the subarray starting with the i-th number to a target S
Memoization to avoid duplication

为每个数字添加了正号或负号-> 过程中有重复计算 example: +1 -1 1 1 1 sum:3
-1 +1 1 1 1 sum:3
求后面三个数字能够得到结果3有多少方法的子问题是重复的计算。
Memoization: 第一次求解后面三个数字能够得到结果3有多少方法的时候，把求解的结果保存下来 (cache) key需要两个变量：从哪个数字开始得到什么结果

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (Math.abs(S) > sum) {
            return 0;
        }
        Map<String, Integer> map = new HashMap<>();
        return dfs(nums, 0, S, map);
    }
    
    private int dfs(int[] nums, int index, int S, Map<String, Integer> map) {
        String encodeString = index + "," + S; // 这里cache放index和S
        if (map.containsKey(encodeString)) {
            return map.get(encodeString);
        }
        if (nums.length == index) { // 递归终止条件：为所有数字添加了正号或负号
            return S == 0 ? 1 : 0;
        }
        int add = dfs(nums, index + 1, S + nums[index], map); // 为第i个数字添加负号
        int minus = dfs(nums, index + 1, S - nums[index], map); // 为第i个数字添加正号
        // dfs index+1 代表下一步要去处理下一个数字
        map.put(encodeString, add + minus);
        return add + minus;
    }
}

Sol 7. Backtracking (D) Optimized (Final Approach)：Pruning + Memoization

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        Map<String, Integer> map = new HashMap<>();
        return dfs(nums, 0, S, sum, map);
    }
    
    private int dfs(int[] nums, int index, int S, int sum, Map<String, Integer> map) {
        String encodeString = index + "," + S;
        if (map.containsKey(encodeString)) {
            return map.get(encodeString);
        }

        if (nums.length == index) { // 递归终止条件：为所有数字添加了正号或负号
            return S == 0 ? 1 : 0; // 当所有数字都处理完之后，S为0说明找到了一个方法
        }
        if (Math.abs(S) > sum) { // 剪枝, 减少不必要的递归路径
            return 0;
        }
        int add = dfs(nums, index + 1, S + nums[index], sum - nums[index], map); // 为第i个数字添加负号
        int minus = dfs(nums, index + 1, S - nums[index], sum - nums[index], map); // 为第i个数字添加正号
        // dfs index+1 代表下一步要去处理下一个数字
        map.put(encodeString, add + minus);
        return add + minus;
    }
}