LeetCode 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、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 目标和（ LeetCode 494 ）：https://leetcode.cn/problems/target-sum/
class Solution{
    public int findTargetSumWays(int[] nums, int target){

        // 每个数字都有两种状态：被进行“+”， 或者被进行“-”
        // 因此可以将数组分成 A 和 B 两个部分
        // A 部分的数字全部进行“+”操作
        // B 部分的数字全部进行“-”操作

        // 设数组的和为 sum ，A 部分的和为 sumA ，B 部分的和为 sumB

        // sumA + sumB = sum (1)
        // 同时有： sumA - sumB = target (2)
        // 将(1)式与(2)式相加，可以得到： 2sumA = sum + target (3)
        // 即 sumA = (sum + target) / 2 
        // 所以，原问题转换为：
        // 有一些物品，第 i 个物品的重量为 nums[i] ， 背包的容量为 sumA ，问：有多少种方式将背包【恰好填满】

        // 先去计算总和
        int sum = 0;

        for (int num : nums) {

            sum += num;

        }

        // 再去计算背包容量
        int bagSize = (target + sum) / 2;

        // 题目有可能出现 target 是一个很小的负数
        // 比如 nums = [ 100 ] ，target = -200
        // 这个时候 bagSize 就是负数了，直接返回0
        if (bagSize < 0) return 0;

        // System.out.println(bagSize);

        // 如果发现 target + sum 为奇数，则无解
        // 比如 nums = [ 1 ] ，target = 2
        // target + sum = 2 + 1 = 3 ，此时无解
        // 因为 bagSize 必然是整数，即 (target + sum) / 2 必然是整数
        // 那么只有 target + sum 为偶数才能得到整数
        if ((target + sum) % 2 == 1) return 0;

        // 在前 i 个数字中，凑出和为 j 的组合有多少种方法
        // dp[0][0] 表示在前 0 个数字中，凑出和为 0 的组合，有多少种方法
        int[][] dp = new int[nums.length + 1][bagSize + 1];

        // 初始化
        for (int i = 0; i <= nums.length; i++) {
            // 在前 i 个数字中，凑出和为 0 的组合有多少种方法
            // 答案是 1 种方法
            // 即每次不选择第 i 个元素就行
            dp[i][0] = 1;
            // System.out.print(dp[i][0] + " ");
        }
        // System.out.println("");

        // 01 背包问题开始填充二维数组
        for (int i = 1; i <= nums.length; i++) {

            for (int j = 0; j <= bagSize; j++) {

                // 注意到 i 是从下标 1 开始访问的
                // 1、背包容量小于当前元素
                // 背包无法放入 nums[i - 1]
                if( j < nums[i - 1]){

                    dp[i][j] = dp[i - 1][j];

                // 2、背包容量大于等于当前元素
                // 背包可以放入 nums[i - 1]
                }else{

                    // 不选：方案数为 dp[i - 1][j]
                    // 选：方案数为 dp[i - 1][j - nums[i - 1]]
                    // 两者之和
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                }
         
            }
        }

        // 返回结果
        return dp[nums.length][bagSize];
    }
}

滚动数组代码

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

        // 每个数字都有两种状态：被进行“+”， 或者被进行“-”
        // 因此可以将数组分成 A 和 B 两个部分
        // A 部分的数字全部进行“+”操作
        // B 部分的数字全部进行“-”操作

        // 设数组的和为 sum ，A 部分的和为 sumA ，B 部分的和为 sumB

        // sumA + sumB = sum (1)
        // 同时有： sumA - sumB = target (2)
        // 将(1)式与(2)式相加，可以得到： 2sumA = sum + target (3)
        // 即 sumA = (sum + target) / 2 
        // 所以，原问题转换为：
        // 有一些物品，第 i 个物品的重量为 nums[i] ， 背包的容量为 sumA ，问：有多少种方式将背包【恰好填满】


        // 先去计算总和
        int sum = 0;

        for (int num : nums) {

            sum += num;

        }

        // 再去计算背包容量
        int bagSize = (target + sum) / 2;

        // 题目有可能出现 target 是一个很小的负数
        // 比如 nums = [ 100 ] ，target = -200
        // 这个时候 bagSize 就是负数了，需要调整为正数
        if (bagSize < 0) bagSize = -bagSize;

        // System.out.println(bagSize);

        // 如果发现 target + sum 为奇数，则无解
        // 比如 nums = [ 1 ] ，target = 2
        // target + sum = 2 + 1 = 3 ，此时无解
        // 因为 bagSize 必然是整数，即 (target + sum) / 2 必然是整数
        // 那么只有 target + sum 为偶数才能得到整数
        if ((target + sum) % 2 == 1) return 0;

        // 在前 i 个数字中，凑出和为 j 的组合有多少种方法

        int[] dp = new int[bagSize + 1];

        // 初始化
        dp[0] = 1;

        // 01 背包问题开始填充二维数组
        for (int i = 1; i <= nums.length; i++) {

            for (int j = bagSize; j >= 0; j--) {

                // 注意到 i 是从下标 1 开始访问的
                // 2、背包容量大于等于当前元素
                // 背包可以放入 nums[i - 1]
                if( j >= nums[i - 1]){

                   dp[j] = dp[j] + dp[j - nums[i - 1]];
               
                }
         
            }
        }

        // 返回结果
        return dp[bagSize];
    } 
}

2 、 C++ 代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {

        // 每个数字都有两种状态：被进行“+”， 或者被进行“-”
        // 因此可以将数组分成 A 和 B 两个部分
        // A 部分的数字全部进行“+”操作
        // B 部分的数字全部进行“-”操作

        // 设数组的和为 sum ，A 部分的和为 sumA ，B 部分的和为 sumB

        // sumA + sumB = sum (1)
        // 同时有： sumA - sumB = target (2)
        // 将(1)式与(2)式相加，可以得到： 2sumA = sum + target (3)
        // 即 sumA = (sum + target) / 2 
        // 所以，原问题转换为：
        // 有一些物品，第 i 个物品的重量为 nums[i] ， 背包的容量为 sumA ，问：有多少种方式将背包【恰好填满】

        // 先去计算总和
        int sum = 0;

        for (int num : nums) {

            sum += num;

        }

        // 再去计算背包容量
        int bagSize = (target + sum) / 2;

        // 题目有可能出现 target 是一个很小的负数
        // 比如 nums = [ 100 ] ，target = -200
        // 这个时候 bagSize 就是负数了，直接返回0
        if (bagSize < 0) return 0;

        // System.out.println(bagSize);

        // 如果发现 target + sum 为奇数，则无解
        // 比如 nums = [ 1 ] ，target = 2
        // target + sum = 2 + 1 = 3 ，此时无解
        // 因为 bagSize 必然是整数，即 (target + sum) / 2 必然是整数
        // 那么只有 target + sum 为偶数才能得到整数
        if ((target + sum) % 2 == 1) return 0;

        // 在前 i 个数字中，凑出和为 j 的组合有多少种方法
        // dp[0][0] 表示在前 0 个数字中，凑出和为 0 的组合，有多少种方法
        vector<vector<int>> dp(nums.size() + 1, vector<int>(bagSize + 1));
        // 初始化
        for (int i = 0; i <= nums.size(); i++) {
            // 在前 i 个数字中，凑出和为 0 的组合有多少种方法
            // 答案是 1 种方法
            // 即每次不选择第 i 个元素就行
            dp[i][0] = 1;
            // System.out.print(dp[i][0] + " ");
        }
        // System.out.println("");

        // 01 背包问题开始填充二维数组
        for (int i = 1; i <= nums.size(); i++) {

            for (int j = 0; j <= bagSize; j++) {

                // 注意到 i 是从下标 1 开始访问的
                // 1、背包容量小于当前元素
                // 背包无法放入 nums[i - 1]
                if( j < nums[i - 1]){

                    dp[i][j] = dp[i - 1][j];

                // 2、背包容量大于等于当前元素
                // 背包可以放入 nums[i - 1]
                }else{

                    // 不选：方案数为 dp[i - 1][j]
                    // 选：方案数为 dp[i - 1][j - nums[i - 1]]
                    // 两者之和
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                }

         
            }
        }

        // 返回结果
        return dp[nums.size()][bagSize];

    }
};

3、Python 代码

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # 每个数字都有两种状态：被进行“+”， 或者被进行“-”
        # 因此可以将数组分成 A 和 B 两个部分
        # A 部分的数字全部进行“+”操作
        # B 部分的数字全部进行“-”操作

        # 设数组的和为 sum ，A 部分的和为 sumA ，B 部分的和为 sumB

        # sumA + sumB = sum (1)
        # 同时有： sumA - sumB = target (2)
        # 将(1)式与(2)式相加，可以得到： 2sumA = sum + target (3)
        # 即 sumA = (sum + target) / 2 
        # 所以，原问题转换为：
        # 有一些物品，第 i 个物品的重量为 nums[i] ， 背包的容量为 sumA ，问：有多少种方式将背包【恰好填满】
        
        # 先去计算总和
        total = sum(nums)

        # 再去计算背包容量
        bagSize = (target + total) // 2

        # 题目有可能出现 target 是一个很小的负数
        # 比如 nums = [ 100 ] ，target = -200
        # 这个时候 bagSize 就是负数了，直接输出0
        if bagSize < 0 : 
            return 0

        # 如果发现 target + sum 为奇数，则无解
        # 比如 nums = [ 1 ] ，target = 2
        # target + sum = 2 + 1 = 3 ，此时无解
        # 因为 bagSize 必然是整数，即 (target + sum) / 2 必然是整数
        # 那么只有 target + sum 为偶数才能得到整数
        if (target + total) % 2 == 1 : return 0

        # 在前 i 个数字中，凑出和为 j 的组合有多少种方法
        # dp[0][0] 表示在前 0 个数字中，凑出和为 0 的组合，有多少种方法
        dp = [[0] * (bagSize + 1) for _ in range(len(nums) + 1)]
        # 初始化
        for  i in range(len(nums) + 1) : 
            # 在前 i 个数字中，凑出和为 0 的组合有多少种方法
            # 答案是 1 种方法
            # 即每次不选择第 i 个元素就行
            dp[i][0] = 1
        

        # 01 背包问题开始填充二维数组
        for i in range( 1 , len(nums) + 1 ) : 

            for j in range(bagSize + 1) :  

                # 注意到 i 是从下标 1 开始访问的
                # 1、背包容量小于当前元素
                # 背包无法放入 nums[i - 1]
                if j < nums[i - 1] : 

                    dp[i][j] = dp[i - 1][j]

                # 2、背包容量大于等于当前元素
                # 背包可以放入 nums[i - 1]
                else:

                    # 不选：方案数为 dp[i - 1][j]
                    # 选：方案数为 dp[i - 1][j - nums[i - 1]]
                    # 两者之和
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]]
    
        # 返回结果
        return dp[len(nums)][bagSize]