【Day 62 】2023-01-01 - 494. 目标和

[azl397985856]

494. 目标和

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/target-sum/

前置知识

• 背包
• 数学

  题目描述

  给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，target。现在你有两个符号  +  和  -。对于数组中的任意一个整数，你都可以从  +  或  -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 target 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], target: 3
输出：5
解释：

-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

一共有5种方法让最终目标和为3。

[Ryanbaiyansong]

··· class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int:

寻找和为target的 方案数

    # + 代表 要当前的数字
    # - 代表 不要当前的数字
    # pos + neg = target 
    # x + -y = target
    # x + -(s-x) = target
    # x - s + x = target 
    # x = (target + s) // 2
    s = sum(nums)
    if (target + s) % 2 or (target + s) < 0:
        return 0

    goal = (target + s) // 2
    f = [0] * (goal + 1)
    f[0] = 1
    for x in nums:
        for i in range(goal, x - 1, -1):
            f[i] += f[i - x]

    return f[-1]

···

[bwspsu]

(Referring to solution)

class Solution:
    def findTargetSumWays(self, nums, target) -> bool:
        t = sum(nums) + target
        if t % 2:
            return 0
        t = t // 2

        dp = [0] * (t + 1)
        dp[0] = 1

        for i in range(len(nums)):
            for j in range(t, nums[i] - 1, -1):
                dp[j] += dp[j - nums[i]]
        return dp[-1]

[chenming-cao]

解题思路

动态规划。我们将所有取正号的数字的和叫做positive，所有取负号的数字的和叫做negative，所有数组的和sum = positive + negative，我们想要达到的target = positive - negative，此题转化为0-1背包问题，我们找到能够组成和为positive的不同子数组的数目即可。接下来求解positive，结合sum和target的公式，positive = (sum + target) / 2。注意特殊情况的判断，sum + target不能为奇数，同时sum要大于等于target的绝对值（positive >= 0 and negative >= 0)。

这里压缩状态，用一维数组dp[j]表示总和为j的不同子数组的个数，状态转移方程：dp[j] = dp[j] + dp[j - nums[i]]。注意这里要用倒序遍历j，因为我们需要未更新的dp[j - nums[i]]来进行计算。

代码

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if (sum < Math.abs(target)) return 0;
        // sum = positive + negative
        // target = positive - negative
        if ((sum + target) % 2 == 1) return 0;

        int positive = (sum + target) / 2;
        // convert to 0-1 Knapsack problem
        int[] dp = new int[positive + 1];
        dp[0] = 1;

        for (int i = 0; i < nums.length; i++) {
            for (int j = positive; j >= 0; j--) {
                // use reverse order. If we use the normal order, dp[j - nums[i]] has already been updated
                if (j >= nums[i]) dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        return dp[positive];
    }
}

复杂度分析

• 时间复杂度：O(positive * n)，positive为正数的和，n为数组长度
• 空间复杂度：O(positive)

[JancerWu]

class Solution {
    Map<String, Integer> memory = new HashMap<>();
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, target, 0, 0);
    }   
    public int dfs(int[] nums, int target, int sum, int index) {
        String key = index + "-" + sum;
        if (memory.containsKey(key)) return memory.get(key);
        if (index == nums.length) {
            memory.put(key, sum == target ? 1 : 0);
            return memory.get(key);
        }
        int ans = dfs(nums, target, sum + nums[index], index + 1) + dfs(nums, target, sum - nums[index], index + 1);
        memory.put(key, ans);
        return ans;
    }
}

[arinzz]

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

}

[snmyj]

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

        findTargetSumWays(nums, target, 0, 0);

        return result;
    }

   void findTargetSumWays(vector<int> nums, int S, int index, int sum) {

        if (index == nums.size()) {

            if (sum == S) {
                result++;
            }
            return;
        }

        findTargetSumWays(nums, S, index + 1, sum + nums[index]);
        findTargetSumWays(nums, S, index + 1, sum - nums[index]);
    }

};

[Alexno1no2]

# 思路和大部分代码来自郁郁雨，增加了target小于0的判断
# 01背包问题是选或者不选，但本题是必须选，是选+还是选-。先将本问题转换为01背包问题。 假设所有符号为+的元素和为x，符号为-的元素和的绝对值是y。 我们想要的 S = 正数和 - 负数和 = x - y 而已知x与y的和是数组总和：x + y = sum 可以求出 x = (S + sum) / 2 = target 也就是我们要从nums数组里选出几个数，令其和为target 于是就转化成了求容量为target的01背包问题 =>要装满容量为target的背包，有几种方案
# 特例判断 如果S大于sum，不可能实现，返回0 如果x不是整数，也就是S + sum不是偶数，不可能实现，返回0; 
# target小于0，返回0
# dp[j]代表的意义：填满容量为j的背包，有dp[j]种方法。因为填满容量为0的背包有且只有一种方法，所以dp[0] = 1
# 状态转移：dp[j] = dp[j] + dp[j - num]， 当前填满容量为j的包的方法数 = 之前填满容量为j的包的方法数 + 之前填满容量为j - num的包的方法数 也就是当前数num的加入，可以把之前和为j - num的方法数加入进来。
# 返回dp[-1]，也就是dp[target]

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        sumAll = sum(nums)
        if S > sumAll or (S + sumAll) % 2:
            return 0
        target = (S + sumAll) // 2
        if target < 0:
            return 0

        dp = [0] * (target + 1)
        dp[0] = 1
        for num in nums:
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] + dp[j - num]
        return dp[-1]

[mayloveless]

思路

题目转化为哪些值目标和为target，target所有负值和，转化为0-1背包的计数问题：状态方程记录每阶段可达重量对应的装法个数。

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function(nums, target) {
    const sum = _.sum(nums);
    if (sum< target) return 0;
    const diff = sum -  target; // a +b == sum; a-b===target
    if (diff % 2 !== 0) {
        return 0;
    }
    target = diff/2;

    // 相当于取哪几个数，总和为len：0-1背包问题
    // 记录每阶段可达重量对应的装法个数。
    const n = nums.length;
    const dp = Array(n+1).fill().map(() => Array(target+1).fill(0));
    dp[0][0] = 1;//target 为0，有1条路径，起始值

    for(let i=1; i<=n; ++i){ //动态规划状态转移
        for (let j=0; j<= target; ++j) {
            if (j-nums[i-1]<0){// 判断是否有效，防止下面的方程不成立
                dp[i][j]=dp[i-1][j];
            } else {
                dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
            }
        }
    }

    return dp[n][target];
};

复杂度

时间：O(n(sum−target)) 空间：O(n(sum−target))

[whoam-challenge]

class Solution: def findTargetSumWays(self, nums: List[int], S: int) -> int: sumAll = sum(nums) if S > sumAll or (S + sumAll) % 2: return 0 target = (S + sumAll) // 2

    dp = [0] * (target + 1)
    dp[0] = 1

    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] + dp[j - num]
    return dp[-1]

[buer1121]

class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int:

    Sum=sum(nums)
    #cnt表示用到加法的数字
    cnt=(Sum+target)//2
    if (Sum+target)%2!=0: return 0
    if abs(target)>Sum: return 0
    dp=[0]*(cnt+1)
    dp[0]=1
    for i in range(len(nums)):
        for j in range(cnt,nums[i]-1,-1):
            dp[j]+=dp[j-nums[i]]

    return dp[cnt]

[Jetery]

class Solution {

    public  int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        if ((sum - target) % 2 != 0 || (sum - target) < 0) return 0;
        int minus = (sum - target) / 2;
        //if (minus == 0) return 1;
        int[][] dp = new int[nums.length + 1][minus + 1];

        for (int i = 0; i <= nums.length; ++i) {
            dp[i][0] = 1;
        }
        // dp[i][j] 前i个数 和为j的组合数
        for (int i = 1; i <= nums.length; ++i) {
            for (int j = 0; j <= minus;++j) {
                if (j - nums[i - 1] >= 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[nums.length][minus];
    }   
}

[zywang0]

class Solution {
    Map<String, Integer> memory = new HashMap<>();
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, target, 0, 0);
    }   
    public int dfs(int[] nums, int target, int sum, int index) {
        String key = index + "-" + sum;
        if (memory.containsKey(key)) return memory.get(key);
        if (index == nums.length) {
            memory.put(key, sum == target ? 1 : 0);
            return memory.get(key);
        }
        int ans = dfs(nums, target, sum + nums[index], index + 1) + dfs(nums, target, sum - nums[index], index + 1);
        memory.put(key, ans);
        return ans;
    }
}

[A-pricity]

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

var findTargetSumWays = function (nums, target) {
    let sum = 0;
    for (const num of nums) {
        sum += num;
    }
    const diff = sum - target;
    if (diff < 0 || diff % 2 !== 0) {
        return 0;
    }
    const n = nums.length, neg = diff / 2;
    const dp = new Array(n + 1).fill(0).map(() => new Array(neg + 1).fill(0));
    dp[0][0] = 1;
    for (let i = 1; i <= n; i++) {
        const num = nums[i - 1];
        for (let j = 0; j <= neg; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= num) {
                dp[i][j] += dp[i - 1][j - num];
            }
        }
    }
    return dp[n][neg];

};

[klspta]

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        if(nums == null){
            return 0;
        }
        return process(nums, 0, target);
    }

    private int process(int[] nums, int index, int target){
        if(index == nums.length){
            return target == 0 ? 1 : 0;
        }
        return process(nums, index + 1, target + nums[index]) + process(nums, index + 1, target - nums[index]);
    }
}

[Dou-Yu-xuan]

class Solution:
    def findTargetSumWays(self, nums, target) -> bool:  
        t = sum(nums) + target  
        if t % 2:   
            return 0  
        t = t // 2  

        dp = [0] * (t + 1)  
        dp[0] = 1  

        for i in range(len(nums)):  
           for j in range(t, nums[i] - 1, -1):  
                dp[j] += dp[j - nums[i]]  
        return dp[-1]  

[bookyue]

code

    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) sum += num;
        if ((sum + target) % 2 != 0 || sum < Math.abs(target)) return 0;

        int positive = (sum + target) / 2;

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

        for (int num : nums) {
            for (int j = positive; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }

        return dp[positive];
    }

[RestlessBreeze]

代码

class Solution {
public:
    int count = 0;

    int findTargetSumWays(vector<int>& nums, int target) {
        backtrack(nums, target, 0, 0);
        return count;
    }

    void backtrack(vector<int>& nums, int target, int index, int sum) {
        if (index == nums.size()) {
            if (sum == target) {
                count++;
            }
        } else {
            backtrack(nums, target, index + 1, sum + nums[index]);
            backtrack(nums, target, index + 1, sum - nums[index]);
        }
    }
};

[ringo1597]

代码

class Solution {
    int count = 0;

    public int findTargetSumWays(int[] nums, int target) {
        backtrack(nums, target, 0, 0);
        return count;
    }

    public void backtrack(int[] nums, int target, int index, int sum) {
        if (index == nums.length) {
            if (sum == target) {
                count++;
            }
        } else {
            backtrack(nums, target, index + 1, sum + nums[index]);
            backtrack(nums, target, index + 1, sum - nums[index]);
        }
    }
}

[tiandao043]

代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(auto num:nums){
            sum+=num;
        }
         if((sum+target)%2||abs(target)>abs(sum))return 0;
        int p=(sum+target)/2;
        int n=nums.size();
        // vector<vector<int>> dp(p+1,vector<int>(n+1));
        vector<int> dp(sum+1);
        dp[0]=1;
        for(int i=0;i<n;i++){
            for(int j=p;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
            }
        }
        // for(int i=0;i<n;i++){
        //     dp[i][0]=1;
        // }

        // for(int i=0;i<=p;i++){   
        //     // cout<<"!!!"<<i<<endl;         
        //     for(int j=1;j<n+1;j++){               
        //         dp[i][j]=dp[i][j-1];
        //         if(i>=nums[j-1]){
        //             dp[i][j]+=dp[i-nums[j-1]][j-1];
        //         }
        //     }
        // }
        return dp[p];
    }
};

还可以递归

class Solution {
public:
    int dfs(vector<int>& nums, uint t,int x){
        if(t==0&&x==nums.size()){
            return 1;
        }
        if(x>=nums.size())return 0;
        int ans=0;
        ans+=dfs(nums,t-nums[x],x+1);
        ans+=dfs(nums,t+nums[x],x+1);
        return ans;
    }
    int findTargetSumWays(vector<int>& nums, int S) {
        return dfs(nums,S,0);
    }
};

时间复杂度：O((negative∗(total+target))/2)

空间复杂度：O((total+target)/2)

[paopaohua]

class Solution {
    int count = 0;

    public int findTargetSumWays(int[] nums, int target) {
        backtrack(nums, target, 0, 0);
        return count;
    }

    public void backtrack(int[] nums, int target, int index, int sum) {
        if (index == nums.length) {
            if (sum == target) {
                count++;
            }
        } else {
            backtrack(nums, target, index + 1, sum + nums[index]);
            backtrack(nums, target, index + 1, sum - nums[index]);
        }
    }
}

[Elon-Lau]

class Solution { int count = 0;

public int findTargetSumWays(int[] nums, int target) {
    backtrack(nums, target, 0, 0);
    return count;
}

public void backtrack(int[] nums, int target, int index, int sum) {
    if (index == nums.length) {
        if (sum == target) {
            count++;
        }
    } else {
        backtrack(nums, target, index + 1, sum + nums[index]);
        backtrack(nums, target, index + 1, sum - nums[index]);
    }
}

}

[FlipN9]

/**
    - 号的元素之和为 neg, + 的元素之和为 sum−neg, neg 和 pos 为 非负偶数
   (sum − neg) − neg = target ==> neg = (sum - target) / 2
   OR
   pos - (sum - pos) = target ==> pos = (target + sum) / 2

    dp[i][j]表示前i个元素有多少个目标和为j的子集。dp[0][0] = 1
        1. 如果 j < num, 则不能选 num, dp[i][j] = dp[i-1][j]
        2. 如果 j>= num, 如果不选 num, dp[i][j] = dp[i-1][j]
                          如果选 num, dp[i][j] = dp[i-1][j-num]

    由于 dp 的每一行的计算只和上一行有关，因此可以使用滚动数组的方式，
        去掉 dp 的第一个维度，将空间复杂度优化到 O(neg).
    实现时，内层循环需采用倒序遍历的方式，这种方式保证转移来的是 dp[i−1][] 中的元素值。

 */
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i : nums) 
            sum += i;
        if (target > sum || target < -sum || (target + sum) % 2 == 1)
            return 0;

        int N = nums.length;
        int neg = (sum - target) / 2;
        int[] dp = new int[neg + 1];
        // base case
        dp[0] = 1;
        // dp
        for (int num : nums) {
            for (int j = neg; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[neg];
    }
}

[Elsa-zhang]

# 494. 目标和
class Solution:
    def findTargetSumWays(self, nums: list[int], target: int):
        n = len(nums)
        total = sum(nums)
        if (total+target)%2 != 0 or (total+target)/2 < 0:
            return 0
        t = int((total+target)/2)

        dp = [[0]*(t+1) for _ in range(n+1)] 
        # for i in range(n+1):
        #     dp[i][0] = 1
        dp[0][0]=1

        for i in range(t+1):
            for j in range(1, len(nums) + 1):
                dp[j][i] = dp[j-1][i]
                if i-nums[j-1] >= 0: 
                    dp[j][i] += dp[j-1][i - nums[j-1]]

        return dp[-1][-1]
nums = [1,1,1,1,1]
target = 3
solution = Solution()
ans = solution.findTargetSumWays(nums, target)
print(ans)