【Day 62 】2023-04-16 - 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。

[Fuku-L]

代码

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 n = nums.length, neg = diff / 2;
        int[][] dp = new int[n+1][neg+1];
        dp[0][0] = 1;
        for(int i = 1; i <= n; 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[n][neg];
    }
}

复杂度分析

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

[Abby-xu]

class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: @lru_cache(None) def rec(index, cur): if index == len(nums): if cur == target: return 1 return 0 return rec(index + 1, cur + nums[index]) + rec(index + 1, cur - nums[index])

    return rec(0, 0)

[huizsh]

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

int sum = 0;
for (int num : nums)
    sum += num;

if (sum < Math.abs(target))
    return 0;

if (((sum + target) & 1) == 1)
    return 0;

sum = (sum + target) / 2;
int[] dp = new int[sum + 1];
dp[0] = 1;

for (int i = 0; i < nums.length; i++)
    for (int j = sum; j >= nums[i]; j--)
        dp[j] = dp[j] + dp[j - nums[i]];

return dp[sum];

[RestlessBreeze]

code

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 (abs(target) > sum) 
            return 0;
        if ((sum + target) % 2 != 0)
            return 0;
        target = (sum + target) / 2;
        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++)
        {
            for (int j = target; j >= nums[i]; j--)
            {
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};

[Meisgithub]

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

    void dfs(const vector<int> &nums, int i, int sum, int target)
    {
        if (i == nums.size())
        {
            if (target == sum)
            {
                ans++;
            }
            return;
        }
        dfs(nums, i + 1, sum - nums[i], target);
        dfs(nums, i + 1, sum + nums[i], target);
    }
};

[zhangyu1131]

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        // dp[i][j]表示由前i个数凑成和j的种数
        // dp[i][j]就等于前i-1个数凑成和为j+nums[i]和j-nums[i]的种数之和
        // 因为j可能是负数，所以数组下标不合适，改成用map试试
        int n = nums.size();
        map<pair<int, int>, int> dp_map1; //(i,j) -> cnt
        dp_map1[make_pair(1, nums[0])] += 1;
        dp_map1[make_pair(1, 0 - nums[0])] += 1;
        map<pair<int, int>, int> dp_map2;

        for (int i = 2; i <= n; ++i)
        {
            for (auto& num_cnt : dp_map1)
            {
                dp_map2[make_pair(i, num_cnt.first.second + nums[i - 1])] += num_cnt.second;
                dp_map2[make_pair(i, num_cnt.first.second - nums[i - 1])] += num_cnt.second;
            }
            dp_map1 = dp_map2;
            dp_map2.clear();
        }

        return dp_map1[make_pair(n, target)];
    }
};

[FireHaoSky]

思路：动态规划，滚动数组

代码：python

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

        dp = [1] + [0] * pos

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

复杂度分析：

"""
时间复杂度：O(n*pos)
空间复杂度：O(pos)
"""

[kofzhang]

思路

动态规划

复杂度

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

代码

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

        neg = s-target
        if neg<0 or neg%2!=0:
            return 0
        neg = neg//2
        dp = [[0]*(neg+1) for _ in range(len(nums)+1)]
        dp[0][0]=1
        for i in range(1,len(nums)+1):
            for j in range(neg+1):
                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(nums)][neg]

[wangzh0114]

class Solution {
public:
    int findTargetSumWays(vector<int> &nums, int target) {
        target += accumulate(nums.begin(), nums.end(), 0);
        if (target < 0 || target % 2) return 0;
        target /= 2;

        int f[target + 1];
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for (int x : nums)
            for (int c = target; c >= x; --c)
                f[c] += f[c - x];
        return f[target];
    }
};

[Hughlin07]

class Solution {

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

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

}

[Diana21170648]

思路

动态规划（背包），滚动数组优化

class Slution:
    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,num[i]-1,-1):
                dp[j]+=dp[j-nums[i]]
                return dp[-1]

**复杂度分析**
- 时间复杂度：O(M*N)
- 空间复杂度：O(N)

[harperz24]

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

        size = (total + target) // 2
        dp = [0] * (size + 1)
        dp[0] = 1

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

        return dp[size]

[chocolate-emperor]

class Solution {
public:

    int mem[24][2004];
    //从长度为len的nums中选择，和等于target的方案数量
    int backtracking(vector<int>&nums,int len, int currSum, int target){
        if(len==0){
            if(currSum==target) return 1;
            return 0;
        }else if(mem[len][currSum+1000]!=-1){
            return mem[len][currSum+1000];
        }

        int add = backtracking(nums,len-1,currSum+nums[len-1],target);
        int sub = backtracking(nums,len-1,currSum-nums[len-1],target);
        mem[len][currSum+1000]  = add + sub;
        return mem[len][currSum+1000];
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int l = nums.size();
        memset(mem,-1,sizeof(mem));
        return backtracking(nums,l,0,target);

    }
};

[joemonkeylee]

思路

对于某一下标i，有且只有两种操作：减去当前下标的数 或 加上当前下标的数。dp[i][sum]表示处理到下标i-1时，得到sum的操作数量 因此：dp[i][sum + num] += dp[i - 1][sum] dp[i][sum - num] += dp[i - 1][sum]

代码

    public int FindTargetSumWays(int[] nums, int target) {
        int n = nums.Length;
        var dp = new List<Dictionary<int, int>>();
        for (int i = 0; i <= n; i++) {
            dp.Add(new Dictionary<int, int>());
        }
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            var num = nums[i];
            foreach(var item in dp[i]) {
                if (!dp[i + 1].ContainsKey(item.Key + num)) {
                    dp[i + 1][item.Key + num] = item.Value;
                }
                else {
                    dp[i + 1][item.Key + num] += item.Value;
                }
                if (!dp[i + 1].ContainsKey(item.Key - num)) {
                    dp[i + 1][item.Key - num] = item.Value;
                }
                else {
                    dp[i + 1][item.Key - num] += item.Value;
                }
            }
        }
        if (!dp[n].ContainsKey(target)) {
            return 0;
        }
        return dp[n][target];
    }

[JasonQiu]

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

        @cache
        def dfs(i, capacity):
            if i < 0:
                return 1 if capacity == 0 else 0
            if capacity < nums[i]:
                return dfs(i - 1, capacity)
            return dfs(i - 1, capacity) + dfs(i - 1, capacity - nums[i])

        return dfs(len(nums) - 1, target)

Time: O(ntarget) Space: O(ntarget)

[bookyue]

TC: O(n^2)
SC: O(n^2)

    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, 0, 0, target, new HashMap<>());
    }

    private int dfs(int[] nums, int idx, int sum, int target, Map<String, Integer> map) {
        String key = idx + "_" + sum;
        if (nums.length == idx) {
            map.put(key, sum == target ? 1 : 0);
            return map.get(key);
        }

        if (map.containsKey(key)) return map.get(key);

        int ans = dfs(nums, idx + 1, sum + nums[idx], target, map)
                + dfs(nums, idx + 1, sum - nums[idx], target, map);

        map.put(key, ans);
        return ans;
    }

[liuajingliu]

解题思路

动态规划

代码实现

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

[kangliqi1]

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

int sum = 0;
for (int num : nums)
    sum += num;

if (sum < Math.abs(target))
    return 0;

if (((sum + target) & 1) == 1)
    return 0;

sum = (sum + target) / 2;
int[] dp = new int[sum + 1];
dp[0] = 1;

for (int i = 0; i < nums.length; i++)
    for (int j = sum; j >= nums[i]; j--)
        dp[j] = dp[j] + dp[j - nums[i]];

return dp[sum];

}

[Lydia61]

494. 目标和

思路

动态规划，背包问题

代码

class Solution {
public:
    int findTargetSumWays(vector<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;
        vector<int> dp(neg + 1);
        dp[0] = 1;
        for (int& num : nums) {
            for (int j = neg; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[neg];
    }
}

复杂度分析

• 时间复杂度：O(m*(sum-target))
• 空间复杂度：O(sum-target)

[yingchehu]

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        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]

[Jetery]

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int n = nums.size();
        int sum = accumulate(nums.begin(), nums.end(), 0);

        if (!(-sum <= S && S <= sum))
            return 0;

        vector<vector<int>> f(n + 1, vector<int>(2 * sum + 1, 0));
        f[0][0 + sum] = 1;

        for (int i = 1; i <= n; i++)
            for (int j = -sum; j <= sum; j++) {
                if (-sum <= j - nums[i - 1])
                    f[i][j + sum] += f[i - 1][j - nums[i - 1] + sum];
                if (j + nums[i - 1] <= sum)
                    f[i][j + sum] += f[i - 1][j + nums[i - 1] + sum];
            }

        return f[n][S + sum];
    }
};

[aoxiangw]

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = {}
        def backtrack(i, total):
            if i == len(nums):
                return 1 if total == target else 0
            if (i, total) in dp:
                return dp[(i, total)]

            dp[(i, total)] = (backtrack(i + 1, total + nums[i]) + backtrack(i + 1, total - nums[i]))
            return dp[(i, total)]
        return backtrack(0, 0)

[lp1506947671]

class Solution:
    def solve(self, nums, target):
        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]

[snmyj]

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 == 1)
            return 0;
        if (Math.abs(target) > sum)
            return 0;
        int bagWeight = (target + sum) / 2;
        int[][] dp = new int[nums.length][bagWeight + 1];
        dp[0][0] = 1; 
        for (int j = 0; j <= bagWeight; j++) {
            if (j == nums[0])
                dp[0][j] = 1; 
            if (j == nums[0] && nums[0] == 0)
                dp[0][j] = 2; 

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

[chanceyliu]

代码

function findTargetSumWays(nums: number[], target: number): number {
  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;
}