LeetCode 494. Target Sum

Problem

LeetCode 494. Target Sum

1. 题目简述

给出一组非负整数nums，和一个目标数S，对每个数字前面我们可以添加正负号，求问一共有多少种添加正负号的方式使得整个数组加和为S。

注意：数组的长度不会超过20；整个数组的加和不会大于1000；返回值一定是32位整形数。

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.

2. 算法思路

参考解法：花花酱LeetCode

这是一道极其经典的老题目了，target sum和0-1背包问题很是相像，并且其能够转化为0-1背包问题，这里一起记录一下整道题的思路吧。

暴力递归

首先，对于本题目，最容易想到的方式自然是暴力递归，DFS来遍历所有可能的分支，时间复杂度为O(2 ^ n)，n为数组数字个数。这道题的输入大小没有超过20，所以2^20勉强在合格范围内，但是依然耗时很长。空间复杂度为O(n)，n也是递归层数。

时间复杂度：O(2 ^ n)，空间复杂度：O(n)。

class Solution {
    // recursion DFS
    public int findTargetSumWays(int[] nums, int S) {
        return findWays(nums, 0, nums.length - 1, S);
    }

    private int findWays(int[] nums, int start, int end, int target) {
        if (start > end) {
            return 0;
        }
        if (start == end && (nums[start] == target || nums[start] == 0 - target)) {
            if (target == 0) {
                return 2;
            }
            return 1;
        }

        return findWays(nums, start + 1, end, target - nums[start]) + findWays(nums, start + 1, end, target + nums[start]);
    }
}

DP 记忆化搜索

我们发现其实我们的重复计算有很多，因为其实对于第i个数而言，它就两种取值方式，正 or 负，前i - 1个数的所有取值种类我们只要算一次就好，不需要正负全算，因此加上一个memo数组，就可以用动态规划来解决了。

memo[i][j]：当前i个数字和为j时，从i（index为i，实际为第i+1）开始（包括i）后面数字所有排列组合满足target为S的可能性有多少种。注意！ 这里的 j 并不是实际的和，因为我们的和有可能是负值，而下标不能为负，所以实际的和为j - offset，offset是nums所有元素的sum和。

base case：memo[0][offset] = 1。用0个元素，和为0（j - offset = 0）的方法有一种。

时间复杂度：O(sum * n)，sum是整体数组的和，因为每个位置上的数字最多被填写一次。

空间复杂度：O(sum * n)，sum是整体数组的和，大小为memo数组的大小。

class Solution {
    // DP top-down
    int[][] memo;
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        memo = new int[nums.length][2 * sum + 1];

        for (int i = 0; i < memo.length; i++) {
            Arrays.fill(memo[i], Integer.MIN_VALUE);
        }

        return dfs(nums, 0, sum, S, 0);
    }

    private int dfs(int[] nums, int sum, int total, int S, int index) {
        if (index == nums.length) {
            if (sum == S) {
                return 1;
            } else {
                return 0;
            }
        } else {
            if (memo[index][sum + total] != Integer.MIN_VALUE) {
                return memo[index][sum + total];
            }

            int add = dfs(nums, sum + nums[index], total, S, index + 1);
            int substract = dfs(nums, sum - nums[index], total, S, index + 1);
            memo[index][sum + total] = add + substract;

            return memo[index][sum + total];
        }
    }
}

DP bottom-up

其实这道题用DP的bottom-up更符合思维一点，因为bottom-up才是正统的DP思想。

首先我们假设dp[i][j]为前i个数，和为j一共有多少种可能的方式。j有两种选择方式，一种是加上当前的第i个数，另一种是减去当前的第i个数，那么我们可以有如下递推式：

$$ dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]] $$

这里要注意，我们的j有可能是负值，实际运算时注意要加上一个offset。

base case：dp[0][0] = 1

Attention：这里有两种递推方式，push和pull，前者是将自身的值，主动推到下一层，另一种是遍历当前值的时候向上一层去拉，二者思路上是一致的，但是需要注意的是写法，i+1还是i-1之类的.

class Solution {
    // DP bottom-up push
    int[][] dp;
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int offset = sum;

        // 注意边界条件的判断！！！
        if (sum < S) {
            return 0;
        }

        // 为什么这里要length+ 1而上面的top-down就不用呢？因为二者dp表示的含义根本就不同，没有可比性！！上面的top - down只是单纯的记录，而不是递推，需要边界case。
        dp = new int[nums.length + 1][2 * sum + 1];
        dp[0][offset] = 1;

        // 这里是push类型，由于会推到i+1层，所以这里i的上限要注意
        for (int i = 0; i < nums.length; i++) {
            // 这里j的遍历是因为我们需要对j-nums[i]和j+nums[i]进行查找，所以缩小一下范围，加速遍历过程。
            for (int j = nums[i]; j < 2 * sum + 1 - nums[i]; j++) {
                // 注意这里的dp方式，是推，不是拉！！！
                dp[i + 1][j + nums[i]] += dp[i][j];
                dp[i + 1][j - nums[i]] += dp[i][j];
            }
        }

        return dp[nums.length][S + offset];
    }
}

class Solution {
    // DP bottom-up pull
    int[][] dp;
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int offset = sum;

        // 注意边界条件的判断！！！
        if (sum < S) {
            return 0;
        }

        dp = new int[nums.length + 1][2 * sum + 1];
        dp[0][offset] = 1;

        // 这里是pull类型，因此从i = 1开始遍历，1层从0层去拉
        for (int i = 1; i <= nums.length; i++) {
            // 这里j的遍历要注意，我们不是从nums[i]开始计算，而是nums[i - 1]，原因在于nums[i - 1]是第i个数，上一种push解法是从当前推以后，所以是nums[i]
            for (int j = 0; j < 2 * sum + 1; j++) {
                if (j - nums[i - 1] >= 0) {
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
                }
                if (j + nums[i - 1] < 2 * sum + 1) {
                    dp[i][j] += dp[i - 1][j + nums[i - 1]];
                }
            }
            /*这里给出一种错误写法，原因在于这次是向上去拉，拉的时候对于最底层的右边界情况来说，它应该拉的两个数中有一个是合法的，另一个是越界的，对于合法的那个我们应该去加，对于不合法的那个，我们不去加。如果按照下面的写法，则二者都不加了，肯定是错误的。*/
            // for (int j = nums[i - 1]; j < 2 * sum + 1 - nums[i - 1]; j++) {
            //     dp[i][j] += dp[i - 1][j - nums[i - 1]] + dp[i - 1][j + nums[i - 1]]
            // }
        }

        return dp[nums.length][S + offset];
    }
}

将问题转化为0-1背包问题

我们假设有P和Q两个集合，P中存放我们设置为正数的数字，Q中我们存放我们设置为负数的数字，因此我们有这样的推导：

已知：
sum(P) - sum(Q) = sum(nums)
sum(P) + sum(Q) = target
二者相加：
sum(P) - sum(Q) + sum(P) + sum(Q) = sum(nums) + target
2 * sum(P) = sum(nums) + target
sum(P) = (sum(nums) + target) / 2

因此，我们将问题转化成了找出所有的正数的集合P，使其的和为 (sum(nums) + target) / 2，这就转变成了一个0-1背包问题。

我们假设dp[i][j]表示前i个元素的子集可以加和为j的可能性有多少种。那么我们有如下递推式：

$$ dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]] $$

我们先用二维数组来表示，然后再将其降维成一维。

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum < S) {
            return 0;
        }
        if ((S + sum) % 2 == 1) {
            return 0;
        }
        int target = (S + sum) / 2;

        int[][] dp = new int[nums.length + 1][target + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] += dp[i - 1][j];
                if (j - nums[i - 1] >= 0) {
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
                }
            }
        }

        return dp[nums.length][target];
    }
}

俺么如何把它降至一维呢？因为它每次计算的时候其实只和上一次计算的值有关，所以每次计算的时候，先copy一份出来做个备份，然后在这个备份上进行操作。

那么为什么直接在备份上操作呢？因为我们i是从小到大遍历的，i + 1里，和为j的可能组合一定包含了i中和为j的可能组合，我们不过是在i的基础上加了一个数而已。

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum < S) {
            return 0;
        }
        if ((S + sum) % 2 == 1) {
            return 0;
        }
        int target = (S + sum) / 2;

        int[] dp = new int[sum + 1];
        dp[0] = 1;

        for (int num : nums) {
            // 注意这里初始化的方式！！！不要新建数组，然后指向dp
            int[] copy = Arrays.copyOfRange(dp, 0, dp.length);
            for (int j = 0; j <= target; j++) {
                if (j - num >= 0) {
                    dp[j] += copy[j - num];
                }
            }
            int y = 0;
        }

        // 注意，这里是target，而不是S！！！
        return dp[target];
    }
}