azl397985856 commented 2 years ago

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。

chakochako commented 2 years ago

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        target = abs(target)
        if total < target: return 0
        dp = [0] * (total + 1)
        dp[total] = 1
        for num in nums:
            for i in range(0, total - 2 * num + 1):
                dp[i] += dp[i + 2 * num]
        return dp[target]

ZJP1483469269 commented 2 years ago

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

        @lru_cache(None)
        def dfs(x , tar):
            if x == n :
                if tar == target:

                    return 1
                else:

                    return 0
            return dfs(x + 1  , tar - nums[x]) + dfs(x + 1 ,tar + nums[x])

        return dfs(0 , 0)

yetfan commented 2 years ago

思路和昨天是一个题

昨天数字可分为两堆相等和为总和的一半target 今天数字分为两堆，一堆正一堆负，加和为target，那我们只需要让负的这一组达到我们想要的结果(sum-target)/2

dp由昨天的true false 修改为求数量， dp[0]从1开始转移方程 dp[j] += dp[j−nums[i]]

代码

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        diff = total - target
        if diff < 0 or diff % 2 != 0:
            return 0

        t = diff // 2
        dp = [1] + [0] * t
        for i, num in enumerate(nums):
            for j in range(t, num - 1, -1):
                dp[j] += dp[j - num]

        return dp[t]

复杂度 时间 O(n*t) 空间 O(t)

zhy3213 commented 2 years ago

思路

转化为背包问题

代码

    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        target=sum(nums)-target
        if target&1 or target<0:
            return 0
        target//=2
        dp=[0]*(target+1)
        dp[0]=1
        for i in nums:
            for j in range(target,i-1,-1):
                dp[j]+=dp[j-i]
        return dp[-1]

QinhaoChang commented 2 years ago

class Solution: def findTargetSumWays(self, nums: List[int], S: int) -> int: nums = [0]+nums @lru_cache(None) def dp(i, total): if i == 0: return total == 0 return dp(i-1, total - nums[i]) + dp(i-1, total + nums[i])

    return dp(len(nums)-1, S)

ZacheryCao commented 2 years ago

Idea

DP

Code

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        if s< target:
            return 0
        dp =[0] * (2 * s + 1)
        dp[nums[0] + s] = 1
        dp[-nums[0] + s] += 1
        for i in nums[1:]:
            tmp = [0] * (2 * s + 1)
            for j in range(-s, s+1):
                if dp[j + s]>0 and j+s+i<=2 * s and j+s-i>=0:
                    tmp[j+s-i] += dp[j+s]
                    tmp[j+s+i] += dp[j+s]
            dp = tmp
        return dp[target+s]

Complexity:

Time: O(total sum * n) Space: O(total sum)

zwx0641 commented 2 years ago

class Solution { public int findTargetSumWays(int[] nums, int target) { int sum = 0; for (int num : nums) { sum += num; } int diff = sum - target; if (diff < 0 || diff % 2 != 0) return 0;

    int half = diff / 2;
    int[] dp = new int[half + 1];
    dp[0] = 1;
    for (int num : nums) {
        for (int i = half; i >= num; i--) {
            dp[i] += dp[i - num];
        }
    }
    return dp[half];
}

}

youzhaing commented 2 years ago

思路

动态规划

code

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # (sum - neg) - neg = target, neg = (sum - target) / 2
        diff = sum(nums) - target
        if diff < 0 or diff % 2 != 0: #为了neg是正整数
            return 0

        neg = diff // 2
        n = len(nums)

        dp = [[0 for i in range(neg + 1)] for j in range(n + 1)]
        dp[0][0] = 1

        for i in range(1, n + 1):
            for j in range(neg + 1):
                dp[i][j] = dp[i - 1][j]
                if nums[i - 1] <= j:
                    dp[i][j] += dp[i - 1][j - nums[i - 1]]
        return dp[n][neg]

复杂度

时间复杂度：O((n+1)*(neg + 1))
空间复杂度：O(n*neg)

Serena9 commented 2 years ago

代码

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]

yan0327 commented 2 years ago

func findTargetSumWays(nums []int, target int) int {
    sum := 0
    for _,x := range nums{
        sum += x
    }
    if sum < target{
        return 0
    }
    total := sum + target
    if total % 2 == 1{
        return 0
    }
    if total < 0{
        return 0
    }
    total /= 2
    dp := make([]int,total+1)
    dp[0] = 1
    for _,num := range nums{
        for j:=total;j>=num;j--{
            dp[j] += dp[j-num]
        }
    }
    return dp[total]
}

Tesla-1i commented 2 years ago

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        diff = total - target
        if diff < 0 or diff % 2 != 0:
            return 0

        t = diff // 2
        dp = [1] + [0] * t
        for i, num in enumerate(nums):
            for j in range(t, num - 1, -1):
                dp[j] += dp[j - num]

        return dp[t]

xinhaoyi commented 2 years ago

494. 目标和

思路一

带记忆的dfs暴力递归

没想到竟然没超时

把问题缩小为一层一层的加，注意加的时候可以是加也可以是加(-1) 即减

总数total要记忆一下，flag和1取异或来反转

代码

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //dfs带记忆的暴力递归
        return dfs(nums, target, 0, 0, 0) + dfs(nums, target, 0, 0, 1);

    }
    //flag = 0 意味着“-” ，flag = 1 意味着“+”
    public int dfs(int[] nums, int target, int pos, int total, int flag){
        if(flag == 0){
            total -= nums[pos];
        }
        else{
            //flag == 1
            total += nums[pos];
        }

        //出口，递归到了最后一层
        if(pos == nums.length - 1){
            if(total == target){
                return 1;
            }
            else{
                return 0;
            }
        }
        return dfs(nums,target,pos+1,total,flag) + dfs(nums,target,pos+1,total,flag ^ 1);
    }
}

思路二

动态规划

01背包问题

参考思路：动态规划思考全过程 - 目标和 - 力扣（LeetCode） (leetcode-cn.com)

根据背包问题的经验，可以将dp(i,j)定义为从数组nums中 0 - i 的元素进行加减可以得到 j 的方法数量。

那么我们就可以将方程定义为：

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

注意j的长度应该是(sum*2)+1，因为要考虑负数，也就是减的部分，以及0

代码

public static int findTargetSumWays(int[] nums, int s) {
    int sum = 0;
    for (int i = 0; i < nums.length; i++)
        sum += nums[i];
    // 绝对值范围超过了sum的绝对值范围则无法得到
    if (Math.abs(s) > Math.abs(sum)) return 0;
    int len = nums.length;
    //因为要包含负数所以要两倍，又要加上0这个中间的那个情况
    int range = sum * 2 + 1;
    //这个数组是从总和为-sum开始的
    int[][] dp = new int[len][range];
    //加上sum纯粹是因为下标界限问题，赋第二维的值的时候都要加上sum
    // 初始化   第一个数只能分别组成+-nums[i]的一种情况
    dp[0][sum + nums[0]] += 1;
    dp[0][sum - nums[0]] += 1;
    for (int i = 1; i < len; i++) {
        for (int j = -sum; j <= sum; j++) {
            if((j+nums[i]) > sum) {
                //+不成立 加上当前数大于了sum   只能减去当前的数
                dp[i][j+sum] = dp[i-1][j-nums[i]+sum]+0;
            }else if((j-nums[i]) < -sum) {
                //-不成立  减去当前数小于-sum   只能加上当前的数
                dp[i][j+sum] = dp[i-1][j+nums[i]+sum]+0;
            }else {
                //+-都可以
                dp[i][j+sum] = dp[i-1][j+nums[i]+sum]+dp[i-1][j-nums[i]+sum];
            }
        }
    }
    return dp[len - 1][sum + s];
}

xuhzyy commented 2 years ago

思路

动态规划（0-1背包问题）

代码

class Solution(object):
    def findTargetSumWays(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if (sum(nums) + target) % 2 != 0:
            return 0
        target = (sum(nums) + target) // 2
        if target < 0:
            return 0
        dp = [0] * (target + 1)
        dp[0] = 1
        # nums.sort()
        for num in nums:
            for j in range(target, num-1, -1):
                dp[j] += dp[j-num]
        return dp[-1]

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N)

LinnSky commented 2 years ago

思路

回溯

代码

     var findTargetSumWays = function(nums, target) {
          let count = 0;
          const backtrack = (nums, target, index, 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]);
              }
          }

          backtrack(nums, target, 0, 0);
          return count;
      };

shamworld commented 2 years ago

var findTargetSumWays = function(nums, target) {
    let total = nums.reduce((a,b)=>a+b,0);
    let diff = total + target;
    if(diff%2||diff<0){
        return 0;
    }
    diff = diff/2;
    let dp = Array(diff + 1).fill(0);
    dp[0] = 1;
    for (const n of nums) {
        for (let i = diff; i >= n; i--) {
            dp[i] += dp[i - n];
        }
    }
    return dp[diff];
};

charlestang commented 2 years ago

思路

动态规划。

所有的数字都是非负数，这是个很重要的条件。
假设填正号的数字总和是 a，填负号的数字总和是 b。则 a + b = allsum 而 a - b = target。
不难得到 a = (allsum + target) / 2 而 b = (allsum - target) / 2。因为 target 有可能是负数，所以，a 也有可能是负数。所以，我们从 b 来着手。
原来的题目变成了，我们挑选一些数字，增加负号，这些数字的总和是 b。变成了一个背包问题。可以使用动态规划来求解。
设 dp[i][j] 表示，前 i 个数字，凑和为 j 的方案数。不难想象， 0 个数字凑 0，有 1 种方案。是为边界。
当 nums[i-1] 大于 j 的时候，方案里不可能包含 nums[i - 1] ，所以 dp[i][j] = dp[i - 1][j]，否则，dp[i][j] = dp[i - 1][j] + dp[i-1][j - nums[i-1]]。

代码

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        allSum = sum(nums)
        if (allSum - target) % 2 != 0: return 0
        t = (allSum - target) // 2
        if t < 0: return 0

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

        for i in range(1, n + 1):
            for j in range(t + 1):
                if nums[i - 1] > j:
                    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][t]

时间复杂度 O(n * target)

空间复杂度O(n * target)

haixiaolu commented 2 years ago

思路

dp + backtracking

代码 / Python

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = {} # (index, total), number of ways

        def backtrack(index, total):
            # base case
            if index == len(nums):
                return 1 if total == target else 0
            if (index, total) in dp: 
                return dp[(index, total)]

            # recursion relation
            dp[(index, total)] = (backtrack(index + 1, total + nums[index]) + 
                                  backtrack(index + 1, total - nums[index]))

            return dp[(index, total)]
        return backtrack(0, 0)

复杂度分析

时间复杂度：O(n)
空间复杂度： O(n)

LannyX commented 2 years ago

思路

背包

代码


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

        for(int i = 1; i <= len; i++){
            int num = nums[i - 1];
            for(int 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[len][neg];
    }
}

732837590 commented 2 years ago

class Solution { int ans = 0; public int findTargetSumWays(int[] nums, int t) { dfs(nums, t, 0, 0); return ans; } void dfs(int[] nums, int t, int u, int cur) { if (u == nums.length) { ans += cur == t ? 1 : 0; return; } dfs(nums, t, u + 1, cur + nums[u]); dfs(nums, t, u + 1, cur - nums[u]); } }

anyingbinglong commented 2 years ago

LannyX发表于32 分钟前思路背包

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

    for(int i = 1; i <= len; i++){
        int num = nums[i - 1];
        for(int 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[len][neg];
}

}

tongxw commented 2 years ago

思路

脑筋急转弯转化为01背包

class Solution {

    public int findTargetSumWays(int[] nums, int target) {
        // pos - neg = target
        // pos + neg  = sum(nums)
        // pos = (target + sum(nums)) / 2;
        int sum = Arrays.stream(nums).sum();
        target += sum;
        if (target % 2 != 0 || target < 0) {
            return 0;
        }

        int positive = target / 2;
        int n = nums.length;

        // 01
        int[] dp = new int[positive + 1];
        dp[0] = 1;
        for (int i=1; i<=n; i++) {
            for (int j=positive; j>=nums[i-1]; j--) {
                dp[j] += dp[j-nums[i-1]];
            }
        }

        return dp[positive];
    }
}

TC: O(n * positive) SC: O(positive)

jiaqiliu37 commented 2 years ago

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]

falconruo commented 2 years ago

思路:

DP + Hashmap

复杂度分析:

时间复杂度: O(N * M)，N为数组nums长度, M = (target + sum)的一半
空间复杂度: O(M)

代码(C++):

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        vector<unordered_map<int, int>> dp(n + 1);
        dp[0][0] = 1;

        for (int i = 0; i < n; ++i) {
            for (auto &a : dp[i]) {
                int sum = a.first, cnt = a.second;
                dp[i + 1][sum + nums[i]] += cnt;
                dp[i + 1][sum - nums[i]] += cnt;
            }

        }
        return dp[n][target];
    }
};

spacker-343 commented 2 years ago

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

1149004121 commented 2 years ago

目标和

思路

背包问题。

代码

var findTargetSumWays = function (nums, target) {
  const sum = nums.reduce((a, b) => a + b, 0);
  let t = sum + target;
  if (t % 2 || t < 0) return 0;
  t = Math.floor(t / 2);
  const dp = Array(t + 1).fill(0);
  dp[0] = 1;
  for (const n of nums) {
    for (let i = t; i >= n; i--) {
      dp[i] += dp[i - n];
    }
  }
  return dp[t];
};

复杂度分析

时间复杂度：O(n * t)。
空间复杂度：O(sum + target)。

callmeerika commented 2 years ago

思路

动态规划

代码

var findTargetSumWays = function (nums, target) {
    let n = nums.length;
    let sum = 0;
    for (let num of nums) {
      sum += num;
    }
    //由x+y=sum;x-y=target;计算得出y=(sum-target)/2;也就是找数组中元素和为(sum-target)/2的子集的数量
    //dp[i][j]表示[0,i]中元素和为j的子集的数量
    if ((sum - target) % 2 === 1 || sum - target < 0) return 0;
    let diff = (sum - target) / 2;
    let dp = new Array(n + 1).fill(0).map(vv => new Array(diff + 1).fill(0));
    dp[0][0] = 1;
    for (let i = 1; i <= n; i++) {
      const num = nums[i - 1];
      for (let j = 0; j <= diff; j++) {
        if (num > j) {
          dp[i][j] = dp[i - 1][j];
        } else {
          dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num];
        }
      }
    }
    return dp[n][diff];
  };

复杂度

时间复杂度：O(n(sum-target))
空间复杂度：O(n(sum-target))

zhangzz2015 commented 2 years ago

思路

转化该问题，TotalSum - 2 part_sum = target part_sum = (TotalSum - target)/2 要注意负数问题。使用两种方法，1种使用backtrack，时间复杂度位O(2^n) 2种使用dp方法，时间复杂度位O(nm)，空间复杂度位 O(n*m)。

关键点

代码

语言支持：C++

C++ Code:


class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        //   sum - 2* val = target 
        //   (sum - target)/2= val  transfer backpack problem. 
        int sum =0; 
        int zero =0; 
        for(int i=0; i< nums.size(); i++)
        {
            if(nums[i]==0)
               zero++; 
            sum += nums[i]; 
        }
        if(target>sum)
            return 0; 
        if((sum - target)%2==1)
            return 0; 
        sum = (sum - target)/2; 
        //  Find numbers to get target sum 
        return findTargetNum(nums, sum) * 1<<(zero); 

    }

    int findTargetNum(vector<int>& nums, int target)
    {
        // dp[i][j]     dp[i-1][j-num[i]] + dp[i-1][j]
        vector<vector<int>> dp(nums.size()+1, vector<int>(target+1, 0));  
        dp[0][0] = 1; 
        for(int i=0; i< nums.size(); i++)
        {
            for(int j=0; j <=target; j++)
            {
                if(j ==0)
                {
                    dp[i+1][j] = 1; 
                }
                else
                {
                    if(j -nums[i]>=0 &&nums[i]!=0)
                    {
                        dp[i+1][j] = dp[i][j-nums[i]] + dp[i][j]; 
                    }
                    else
                        dp[i+1][j] = dp[i][j]; 
                }
            }
        }
        return dp[nums.size()][target]; 

    }

    int backTracMethod(vector<int>& nums, int target)
    {
        int sum =0; 
        for(int i=0; i< nums.size(); i++)
            sum += nums[i]; 
        if(target>sum)
            return 0; 

        int onePath =0; 
        int ret =0; 
        backTrac(nums, onePath, sum, target, 0, ret);         
        return ret;         
    }

    void backTrac(vector<int>& nums, int& onePath, int sum, int target, int start, int& ret)
    {

       // cout << "onePath:" << onePath << "\n"; 
        if(sum - 2* onePath == target)
            ret++;
        else if(sum - 2* onePath < target)
            return; 
        for(int i = start; i< nums.size(); i++)
        {
            onePath += nums[i]; 
            backTrac(nums, onePath, sum, target, i+1, ret); 
            onePath -= nums[i]; 
        }

    }
};

last-Battle commented 2 years ago

代码

语言支持：C++

C++ Code:


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

        helper(nums, 0, 0, target, res);

        return res;
    }

    void helper(vector<int>& nums, int start, int sum, int target, int& res) {
        if (start == nums.size()) {
            if (sum == target) {
                ++res;
            }
            return;
        } 

        helper(nums, start + 1, sum + nums[start], target, res);

        helper(nums, start + 1, sum + (-1) * nums[start], target, res);
    }
};

alongchong commented 2 years ago

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

hdyhdy commented 2 years ago

func findTargetSumWays(nums []int, target int) int {
    sum := 0
    for _, v := range nums {
        sum += v
    }
    diff := sum - target
    if diff < 0 || diff%2 == 1 {
        return 0
    }
    n, neg := len(nums), diff/2
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, neg+1)
    }
    dp[0][0] = 1
    for i, num := range nums {
        for j := 0; j <= neg; j++ {
            dp[i+1][j] = dp[i][j]
            if j >= num {
                dp[i+1][j] += dp[i][j-num]
            }
        }
    }
    return dp[n][neg]
}

Riuusee commented 2 years ago

思路

背包转移方程：dp[j] += dp[j - nums[i]]

代码

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

        return dp[size];
    }
}

stackvoid commented 2 years ago

思路

背包问题

代码

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]);
        }
    }
}

复杂度

TIme O(2^n) Space O(N)

LAGRANGIST commented 2 years ago

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # (sum - neg) - neg = target, neg = (sum - target) / 2
        diff = sum(nums) - target
        if diff < 0 or diff % 2 != 0: #为了neg是正整数
            return 0

        neg = diff // 2
        n = len(nums)

        dp = [[0 for i in range(neg + 1)] for j in range(n + 1)]
        dp[0][0] = 1

        for i in range(1, n + 1):
            for j in range(neg + 1):
                dp[i][j] = dp[i - 1][j]
                if nums[i - 1] <= j:
                    dp[i][j] += dp[i - 1][j - nums[i - 1]]
        return dp[n][neg]

Myleswork commented 2 years ago

思路

可以转换成背包问题

背包容量为(sum+target)/2，元素为物品，元素值为物品重量，忽略元素价值

可以进行状态压缩

代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(),nums.end(),0);
        if((sum-target)%2) return 0;
        int len = nums.size();
        sum = sum-(sum-target)/2;
        if(sum<0) return 0;
        vector<vector<int>> dp(len+1,vector<int>(sum+1,0));
        dp[0][0] = 1;
        for(int i = 1;i<=len;i++){
            for(int j = 0;j<=sum;j++){
                dp[i][j] = dp[i-1][j];
                if(j>=nums[i-1]) dp[i][j] += dp[i-1][j-nums[i-1]];
            }
        }
        return dp[len][sum];
    }
};

复杂度分析

时间复杂度：O(len*sum)

空间复杂度：O(len*sum)

moirobinzhang commented 2 years ago

Code:

public class Solution {

public int count = 0;

public int FindTargetSumWays(int[] nums, int target) {
    Caculate(nums,  target, 0, 0);
    return count;        
}

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

}

Toms-BigData commented 2 years ago

func findTargetSumWays(nums []int, target int) int { sum:=0 for i := 0; i < len(nums); i++ { sum+=nums[i] } diff := sum-target if diff <0 || diff%2==1{ return 0 } n, neg := len(nums), diff/2 dp := make([][]int, n+1) for i := range dp { dp[i] = make([]int, neg+1) } dp[0][0] = 1 for i, num := range nums{ for j := 0; j <= neg; j++ { dp[i+1][j] = dp[i][j] if j >= num{ dp[i+1][j] += dp[i][j-num] } } } return dp[n][neg] }

machuangmr commented 2 years ago

代码

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]);
        }
    }
}

biscuit279 commented 2 years ago

思路：

动态规划

class Solution(object):
    def findTargetSumWays(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) == 1:
            if nums[0] == target or nums[0] == -target:
                return 1
            else:
                return 0
        if len(nums) < 1 :
            return 0
        #dp[i][j]表示前i个数组成运算结果为j的表达式的数量
        if (sum(nums) + target) % 2 == 1 :
            return 0
        t = (sum(nums) + target) // 2
        dp = [[0]*(len(nums)+1) for _ in range(t+1)]
        dp[0][0] = 1
        for i in range(t+1):
            for j in range(1,len(nums)+1):
                dp[i][j] = dp[i][j-1]
                if i - nums[j-1] >= 0 :
                    dp[i][j] += dp[i-nums[j-1]][j-1]
        return dp[-1][-1]

时间复杂度：O(mn) 空间复杂度：O(mn)

liuajingliu commented 2 years ago

代码实现

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 neg = Math.floor(diff / 2);
    const dp = new Array(neg + 1).fill(0);
    dp[0] = 1;
    for (const num of nums) {
        for (let j = neg; j >= num; j--) {
            dp[j] += dp[j - num];
        }
    }
    return dp[neg];
};

复杂度分析

时间复杂度：$O(n×(sum−target))$，其中 n 是数组nums的长度，sum 是数组 nums 的元素和，target 是目标数。
空间复杂度：$O(sum−target)$, 其中 sum 是数组nums的元素和，target 是目标数

GaoMinghao commented 2 years ago

思路

好难过😫，完全没想到是背包问题的变形，还在思考怎么用回溯写，也没写出来。。。

代码

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

z1ggy-o commented 2 years ago

思路

回溯暴力解了。

DP 没能理解，之后再学习

代码

class Solution {
public:
    int cnt;
    int findTargetSumWays(vector<int>& nums, int target) {
        backtrack(nums, target, 0, 0);
        return cnt;
    }

    void backtrack(vector<int>& nums, int target, int idx, int sum)
    {
        if (idx == nums.size()) {  // reach the end
            if (sum == target)
                cnt++;
        } else {
            backtrack(nums, target, idx + 1, sum + nums[idx]);
            backtrack(nums, target, idx + 1, sum - nums[idx]);
        }
    }
};

复杂度分析

时间：O(2^n)
空间：O(n)

Hacker90 commented 2 years ago

class Solution { public int findTargetSumWays(int[] nums, int target) { int sum = 0; for (int num : nums) { sum += num; } int diff = sum - target; if (diff < 0 || diff % 2 != 0) return 0;

int half = diff / 2;
int[] dp = new int[half + 1];
dp[0] = 1;
for (int num : nums) {
    for (int i = half; i >= num; i--) {
        dp[i] += dp[i - num];
    }
}
return dp[half];

} }

CodingProgrammer commented 2 years ago

思路1-回溯枚举

class Solution {

    private List<List<Integer>> res = new ArrayList();
    private Deque<Integer> path = new LinkedList();

    public int findTargetSumWays(int[] nums, int target) {
        if (nums == null || nums.length == 0) return 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (target > sum) return 0;
        if (((target + sum) & 1) == 1) return 0;

        Arrays.sort(nums);
        backtracking(nums, (sum + target) / 2, 0);
        // System.out.println(res);
        return res.size();
    }

    private void backtracking(int[] nums, int target, int indexStart) {
        if (target == 0) {
            res.add(new ArrayList(path));
        }

        for (int i = indexStart; i < nums.length && target >= nums[i]; i++) {
            path.addLast(nums[i]);
            backtracking(nums, target - nums[i], i + 1);
            path.removeLast();
        }
    }
}

时间复杂度：O(2^N)
空间复杂度：O(N)

思路2-动态规划之01背包

这道题不好想:

x - y = target
x + y = sum

综上：x = (target + sum) / 2，将问题转化为求背包容量为 (target + sum) / 2 的01背包问题，但是本题是求方案数，所以递推公式为 dp[j] = dp[j] + dp[j - num]

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException();
        }
        int sum = Arrays.stream(nums).sum();
        if (sum < Math.abs(target) || ((sum + target) & 1) != 0) return 0;
        int size = (sum + target) >> 1;
        // dp[j] 表示从数组中取出和为 j 的方法数
        // dp[j] = dp[j] + dp[j - num];
        int[] dp = new int[size + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = size; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }

        return dp[size];
    }
}

时间复杂度：O(N * (sum + target) / 2)
空间复杂度：O((sum + target) / 2))

zzzpppy commented 2 years ago

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

Richard-LYF commented 2 years ago

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

    s = sum(nums)
    if target > s or (target + s)%2:
        return 0

    t = (s + target) // 2
    if t<0:
        return 0
    dp = [0] * (t + 1)
    dp[0] = 1

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

    return dp[-1]

fornobugworld commented 2 years ago

传统背包

有以下几个点要注意：1、dp[0][0] =1 2、target不规范，要考虑负数大于总和等越界问题3、递推公式也要考虑二维数组坐标为正 ··· py class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int:

A-B = target

    #A+B= sum
    #A= (sum +target)/2
    sums = 0
    for num in nums:
        sums +=num
    if (sums + target) %2 ==1:
        return 0
    target = (sums + target)//2
    if target < 0:
        return 0
    length = len(nums)
    #dp[i][j]前i个整数恰好为j的数目
    dp = [[0]* (target+1) for _ in range(length+1)]
    dp[0][0] =1
    for i in range(1,length+1):
        for j in range(target+1):
            if j >=nums[i-1]:
                dp[i][j] = dp[i-1][j-nums[i-1]]+dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j]
    return dp[length][target]

···

hx-code commented 2 years ago

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

for123s commented 2 years ago

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

        };
        return dp[sum];
    }
};

ChenJingjing85 commented 2 years ago

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        self.res = 0
        temp = 0
        def cal(i, temp):      
            if i == len(nums):
                if temp == target:
                    self.res += 1
            else:
                cal(i+1, temp+nums[i])
                cal(i+1, temp-nums[i])
        cal(0,0)
        return self.res

FlorenceLLL commented 2 years ago

题目类型：DP

代码

class Solution {
    public static int findTargetSumWays(int[] nums, int s) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        // 超过sum最大值，没有办法得到
        if (Math.abs(s) > Math.abs(sum)) return 0;

        int len = nums.length;
        // - 0 +
        int t = sum * 2 + 1;
        int[][] dp = new int[len][t];
        // 初始化
        if (nums[0] == 0) {
            dp[0][sum] = 2;
        } else {
            dp[0][sum + nums[0]] = 1;
            dp[0][sum - nums[0]] = 1;
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < t; j++) {
                // 边界
                int l = (j - nums[i]) >= 0 ? j - nums[i] : 0;
                int r = (j + nums[i]) < t ? j + nums[i] : 0;
                dp[i][j] = dp[i - 1][l] + dp[i - 1][r];
            }
        }
        return dp[len - 1][sum + s];
    }

}

leetcode-pp / 91alg-6-daily-check

【Day 62 】2022-02-11 - 494. 目标和 #72

494. 目标和

入选理由

题目地址

前置知识

题目描述

思路

代码

Idea

Code

Complexity:

思路

code

复杂度

代码

494. 目标和

思路一

代码

思路二

代码

思路

代码

思路

代码

思路

代码

思路

代码 / Python

复杂度分析

思路

代码

思路

思路

代码

复杂度

思路

关键点

代码

代码

思路

代码

思路

代码

复杂度

思路

代码

代码

思路：

代码实现

复杂度分析

思路

代码

思路

代码

思路1-回溯枚举

思路2-动态规划之01背包

传统背包

A-B = target

代码