494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 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
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

思路

1. 递归

class Solution {

    int result = 0;

    public int findTargetSumWays(int[] nums, int target) {
        find(nums, target, 0);
        return result;
    }

    public void find(int[] nums, int target, int n) {
        if (n == nums.length) {
            if (target == 0) {
                result++;
            }
            return;
        }
        find(nums, target - nums[n], n + 1);
        find(nums, target + nums[n], n + 1);
    }
}

3. 背包

这道题目咋眼一看和动态规划背包啥的也没啥关系。

本题要如何使表达使结果为 target，

既然为 target，那么就一定有 left 组合 - right 组合 = target。

left + right 等于 sum，而 sum 是固定的。

公式来了， left - (sum - left) = target -> left = (target + sum)/2 。

target是固定的，sum是固定的，left就可以求出来。

此时问题就是在集合nums中找出和为left的组合。

1. 确定dp数组以及下标的含义

   dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法。

   其实也可以使用二维dp数组来求解本题，dp[i][j]：使用下标为 [0, i] 的 nums[i] 能够凑满 j（包括j）这么大容量的包，有dp[i][j]种方法。

2. 确定递推公式

   不考虑 nums[i] 的情况下，填满容量为 j - nums[i] 的背包，有 dp[j - nums[i]] 种方法。

   那么只要搞到 nums[i] 的话，凑成 dp[j] 就有 dp[j - nums[i]] 种方法。

   递推公式为：dp[j] += dp[j - nums[i]]

   为什么要加上 dp[j] ?

   假如为二维数组时，dp[i][j] 表示 使用下标为[0, i]的数字，最终结果为 dp[0][j] + dp[1][j] + dp[2][j] + ... + dp[n][j]，如果要使用一维数组的话，需要新一轮的 dp[j] 需要类加上前一轮的 dp[j]，即 dp[j] += dp[j - nums[i]]

3. 初始化 初始化dp[0] = 1，为什么？此时代表left = 0，即所有值都属于right。而且如果不设置为 1，dp[j] += dp[j - nums[i]]的结果将一直为 0。

class Solution {

    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        // 0 <= nums[i] <= 1000
        if (Math.abs(target) > sum) {
            return 0;
        }
        // (left - right = target && left - right = target) -> left * 2 = sum + target
        int leftDoule = target + sum;
        // 判断 leftDoule 是否为偶数
        if (leftDoule % 2 == 1) {
            return 0;
        }
        int left = leftDoule / 2;
        int[] dp = new int[left + 1];

        //此时代表left = 0，即所有值都属于right
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = left; j >= nums[i]; j--) {
                // 需要累加
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[left];
    }
}