【Day 62 】2021-11-10 - 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。

[yanglr]

思路:

可以用回溯来做, 比较慢。

用动态规划快一些。

方法: 动态规划

题意: -1000 <= target <= 1000 且 sum(nums[i]) <= 1000, 故后面需要用作+offset确保dp数组的index >= 0 .

dp数组的选用

dp[i][S]: 用前i个数进行计算后得到和为S的方法的数量.

dp数组的第2维统一 +sum确保这一维的index >= 0

寻找dp[i][S]与它前面状态的关系

根据dp的无后效性，找dp[i][S]与之前状态的关系~

当新加入一个数 nums[i]时, 考虑加入这个数前后的变化。

dp[i][S] = dp[i-1][...]

S,    S+nums[i] / S-nums[i]

i-1        i          i

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

注意: 填充dp数组第2维时, 需要+sum作为offset 确保这一维的index >= 0 .

代码:

实现语言: C++

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        nums.insert(nums.begin(), 0);
        const int N = nums.size();
        int sum = 0;
        for (int& x : nums) sum += x; /* 题意: sum(nums[i]) <= 1000, 后面需要用作+offset确保dp数组的index >= 0 */
        if (target > sum || target < -sum) return 0;
        auto dp = vector<vector<int>>(N, vector<int>(2 * sum + 1, 0));
        dp[0][0 + sum] = 1; /* dp[i][S]: 用前i个数进行计算后得到和为S的方法的数量.
                               dp数组的第2维统一 +sum确保这一维的index >= 0 
                            */
        for (int i = 1; i < N; i++)
        {
            for (int s = -sum; s <= sum; s++)
            {
                if (s + nums[i] + sum <= 2 * sum)
                    dp[i][s + nums[i] + sum] += dp[i - 1][s + sum];
                if (s - nums[i] + sum >= 0)
                    dp[i][s - nums[i] + sum] += dp[i - 1][s + sum];
            }
        }
        return dp[N - 1][target + sum];
    }
};

复杂度分析:

• 时间复杂度: O(n * S), n是nums数组中元素的个数, S是sum的种类数, -1000~1000, S=2000
• 空间复杂度: O(n * S)

[ysy0707]

思路：动态规划 背包

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int i: nums){
            sum += i;
        }
        //把所有符号为正的数总和设为一个背包的容量，容量为x；把所有符号为负的数的绝对值总和设为一个背包的容量，容量为y。
        //在给定的数组中，有多少种选择方法让背包装满。令sum为数组的总和，则x+y = sum。而两个背包的差为S,则x-y=target。从而求得x=(target+sum)/2。
        //基于上述分析，题目转换为背包问题：给定一个数组和一个容量为x的背包，求有多少种方式让背包装满。
        //背包容量为整数，sum + target 为奇就说明不存在满足要求的数
        // 背包容量为整数，sum+S为奇数的话不满足要求
        if ((sum + target) % 2==1){
            return 0;
        }
        // 目标和不可能大于总和
        if (target > sum){
            return 0;
        }

        int x = (sum + target) / 2;
        int[] dp = new int[x + 1];
        //dp[j]代表的意义：填满容量为j的背包，有dp[j]种方法。因为填满容量为0的背包有且只有一种方法，所以dp[0] = 1
        dp[0] = 1;

        //当前填满容量为j的包的方法数 = 之前填满容量为j的包的方法数 + 之前填满容量为j - num的包的方法数
        //也就是当前数num的加入，可以把之前和为j - num的方法数加入进来。
        for(int num: nums){
            for(int i = x; i >= num; i--){
                dp[i] = dp[i] + dp[i - num];
            }
        }
    return dp[x];
    }
}

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

[last-Battle]

思路

关键点

• DFS爆搜

代码

• 语言支持：C++

C++ Code:

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

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n!)$
• 空间复杂度：$O(n)$

[kidexp]

thoughts

背包问题 dp[i+1][num] 表示前面i个数通过上面的运算组成num的方式有多少个

我们可以根据 dp[i]来推算dp[i+1] 通过遍历所有的num和当前的nums[i]进行组合

通过滚动数组来优化

code

from collections import defaultdict

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = [{0: 1}, {}]
        n = len(nums)
        for i in range(n):
            dp[(i + 1) % 2] = defaultdict(int)
            for num, num_ways in dp[i % 2].items():
                dp[(i + 1) % 2][num - nums[i]] += num_ways
                dp[(i + 1) % 2][num + nums[i]] += num_ways
        return dp[n % 2][target]

complexity

时间复杂度: O(n * sum), sum是nums所有元素相加的和，那么范围就是-sum 到 sum

空间复杂度: O(n *sum )

[mmboxmm]

代码

class Solution {
  public int findTargetSumWays(int[] nums, int target) {
    Map<String, Integer> dp = new HashMap<>();
    return explore(nums, target, 0, dp);
  }

  public int explore(
    int[] nums,
    int target, 
    int currIdx,
    Map<String, Integer> dp
  ) {
    if(target == 0 && currIdx == nums.length) return 1;
    String key = String.valueOf(target) + "," + String.valueOf(currIdx);
    if(dp.get(key) != null) return dp.get(key);
    if(currIdx >= nums.length) return 0;

    int res1 = explore(nums, target-nums[currIdx], currIdx+1, dp);
    int res2 = explore(nums, target+nums[currIdx], currIdx+1, dp);
    int ways = res1 + res2;

    dp.put(key, ways);
    return ways;
  }
}

[Zhang6260]

JAVA版本

思路：该题使用dfs与背包都可以通过，但是背包的方式效果是最高的，（刚开始看这题只想到了dfs，当看了解析的看几行后，瞬间就明白该题就是昨天题的换皮啊！）因为是不重复的使用，外循环使用数组的大小作为遍历的变量，并且内循环从大到小的进行遍历。

//背包
class Solution {
   public int findTargetSumWays(int[] nums, int target) {
       //注意该题的要明白其中的规律
       if(nums.length==1){
           if(nums[0]==target||nums[0]==-1*target){
               return 1;
           }else return 0;
       }
       int all=0;
       for(int i:nums)all+=i;
       int t=(all+target);
       if(t%2==1)return 0;
       int temp =t/2;
       Arrays.sort(nums);
       int []dp =new int[temp+1];
       dp[0] =1;
       for(int i=0;i<nums.length;i++){
           for(int j=temp;j>=nums[i];j--){
               dp[j]+=dp[j-nums[i]];
           }
       }
       return dp[temp];
   }
}
//dfs
class Solution {
   int res = 0;
   public int findTargetSumWays(int[] nums, int target) {

       dfs(nums,target,0,0);
       return res;
   }
   public void dfs(int[]arr,int target,int temp,int i){

       if(i==arr.length&&temp==target){
           res++;
           return;
       }
       if(i>=arr.length)return;
       dfs(arr,target,temp+arr[i],i+1);
       dfs(arr,target,temp-arr[i],i+1);
   }

}

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

空间复杂度：O(N）

[yingliucreates]

link:

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

代码 Javascript

const findTargetSumWays = function(nums, S) {
  let sums = new Map([[0, 1]]);

  for (let num of nums) {
    const next = new Map();

    for (let [sum, amount] of sums) {
      const plus = sum + num;
      const minus = sum - num;

      next.set(plus, next.has(plus) ? next.get(plus) + amount : amount);
      next.set(minus, next.has(minus) ? next.get(minus) + amount : amount);
    }

    sums = next;
  }

  return sums.has(S) ? sums.get(S) : 0;
};

[yachtcoder]

DFS + Memo O(nS), O(nS)

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        @cache
        def dfs(idx, cur):
            if idx == len(nums):
                return int(cur == target)
            ret = dfs(idx+1, cur+nums[idx])
            ret += dfs(idx+1, cur-nums[idx])
            return ret
        return dfs(0, 0)

[ZiyangZ]

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i: nums) sum += i;
        if (Math.abs(target) > sum) return 0;
        int[][] dp = new int[nums.length][sum * 2 + 1];

        dp[0][nums[0] + sum] = 1;
        dp[0][sum - nums[0]] += 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= 2 * sum; j++) {
                if (j - nums[i] < 0) {
                    dp[i][j] = dp[i-1][j+nums[i]];
                } else if (j + nums[i] > 2 * sum) {
                    dp[i][j] = dp[i-1][j-nums[i]];
                } else {
                    dp[i][j] = dp[i-1][j+nums[i]] + dp[i-1][j-nums[i]];
                }

            }
        }
        return dp[nums.length - 1][target + sum];
    }
}

[Daniel-Zheng]

思路

回溯。

代码(C++)

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

复杂度分析

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

思路

动态规划。

代码(C++)

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(N^2)
• 空间复杂度：O(N)

[pan-qin]

Idea:

We can either add nums[i] or minus nums[i] to get sum target. Whether add or minus only depend on the sum we got from nums[i-1]. So use DP. The sum range that can be achieved is [-sum, sum], here sum is the sum of abs(nums[i]). Use dp array[][], dp[i+1][j] store the number of ways to add/minus nums[0]...nums[i] and get sum j. So dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]]. Since the range of j is [-sum, sum], we need to shift each j by +sum, in order to calculate the [-sum, 0] range. Base case dp[0][sum]=1;

Complexity:

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

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n=nums.length;
        int sum=0;
        for(int num: nums)
            sum+=num;
        if(target>sum || target<-sum)
            return 0;
        int[][] dp = new int[n+1][sum*2+1];
        //j need to right shift of sum
        dp[0][sum]=1;
        for(int i=1;i<=n;i++) {
            int val=nums[i-1];
            for(int j=-sum;j<=sum;j++) {    
                if(j-val+sum>=0)
                    dp[i][j+sum]+=dp[i-1][j-val+sum];
                if(j+val+sum<=2*sum)
                    dp[i][j+sum]+=dp[i-1][j+val+sum];             
            }
        } 
        return dp[n][target+sum];

    }
}

[biancaone]

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        return self.memo_search(nums, 0, 0, target, {})

    def memo_search(self, nums, index, cur_sum, target, memo):
        if (index, cur_sum) in memo:
            return memo[(index, cur_sum)]
        if index == len(nums):
            if cur_sum == target:
                return 1
            else:
                return 0

        result = self.memo_search(nums, index + 1, cur_sum + nums[index], target, memo) + self.memo_search(nums, index + 1, cur_sum - nums[index], target, memo)

        memo[(index, cur_sum)] = result

        return result

[xinhaoyi]

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

[james20141606]

Day 62: 494. Target Sum (DP, knapsack, recursion)

• Problem Link

  • 494. Target Sum

• Ideas

  • the key is to convert this problem to a 0-1 knapsack problem! From pos + neg = target and pos - neg = sum(nums)/total, we have pos = (total + target) / 2 = t. If t < 0 return 0. Now it is a knapsack problem! each number has weight = num and their values are all 1. We could select each number once, and t is the total capacity!
  • the original 2D version should be: dp[i][j] means selecting from first i element and sum up to j. dp[0][0] = 1 and dp[0][j] = 0 if j > 0. Then we loop through all the number in nums and loop through 0 to t, if j<num, could not select, so dp[i][j]=dp[i−1][j]; If j≥num, we could select num or not, so we have: dp[i][j]=dp[i−1][j]+dp[i−1][j−num].
  • Then we use 1D dp and loop from t to nums[i] - 1, dp[0] = 1(choose nothing, one solution). use dp[j] += dp[j - nums[i]] to update

• Complexity: hash table and bucket

  • Time: O(neg * (total + tar) / 2)
  • Space: O((total + tar) / 2)

• Code

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

        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]

from collections import defaultdict
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = [{0: 1}, {}]
        n = len(nums)
        for i in range(n):
            dp[(i + 1) % 2] = defaultdict(int)
            for num, num_ways in dp[i % 2].items():
                dp[(i + 1) % 2][num - nums[i]] += num_ways
                dp[(i + 1) % 2][num + nums[i]] += num_ways
        return dp[n % 2][target]

class Solution:    
    def findTargetSumWays(self, A, S):
        count = collections.Counter({0: 1})
        for x in A:
            step = collections.Counter()
            for y in count:
                step[y + x] += count[y]
                step[y - x] += count[y]
            count = step
        return count[S]

class Solution:
    def findTargetSumWays(self, nums, target) -> bool:
        t = sum(nums) + target
        if t % 2:
            return 0
        t = t // 2
        if t < 0: return 0
        dp = [[0] * (t + 1) for _ in range(len(nums) + 1)]
        dp[0][0] = 1
        for i in range(1, len(nums) + 1):
            num = nums[i - 1]
            for j in range(t + 1):
                if num > j:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num]
        #print (dp)
        return dp[-1][-1]

#recursion:
class Solution:
    def findTargetSumWays(self, nums, target):
        @lru_cache(None)
        def f(i, cur_sum):
            if i == len(nums):
                if target == cur_sum:
                    return 1
                return 0

            return f(i + 1, cur_sum + nums[i]) + f(i + 1, cur_sum - nums[i])

        return f(0, 0)

• other resources:
  • https://leetcode.com/problems/target-sum/discuss/455024/DP-IS-EASY!-5-Steps-to-Think-Through-DP-Questions.
  • https://leetcode-cn.com/problems/target-sum/solution/mu-biao-he-by-leetcode-solution-o0cp/
  • https://leetcode-solution.cn/solutionDetail?type=3&id=62&max_id=2

[zjsuper]

Idea change to 0-1 knapsack problem Time: O(neg * (total + tar) / 2) Space: O((total + tar) / 2)

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

        #dp[i][j] num of ways sum to J using 0:i num
        if (sum(nums)+target) %2 ==1:
            return 0

        t = (sum(nums)+target) //2
        if t <0:
            return 0
        dp = [[0 for _ in range(len(nums)+1)] for _ in range(t+1)]
        print(dp)
        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]:
                    dp[i][j] += dp[i-nums[j-1]][j-1]
        return dp[-1][-1]

[zhy3213]

思路

暴 力 动 规

代码

    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s=[0]*2001
        s[nums[0]]+=1
        s[-nums[0]]+=1
        for i in nums[1:]:
            l=[0]*2001
            for j in range(-1000,1001):
                if j-i>-1001:
                    l[j]+=s[j-i]
                if j+i<1001:
                    l[j]+=s[j+i]
            s=l
        return s[target]

看了题解 我果然是five 学会昨天的想不出今天的

[Yufanzh]

Intuition

This problem can be converted to a 01 backpack problem\ using + and - to combine numbers. Then let's name all the positive sum = pos\ and name all the negative sum = neg\ the sum of all numbers in nums to be "total"\ Then we have pos + neg = target\ pos - neg = total\ Then pos = (total + target)/2 --> this convert it to be lc416\ this is a 01 backpack problem, use DP approach + considering all corner cases

Algorithm in python3

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

        # corner case 1
        if (sum(nums) + target) % 2:
            return 0
        # corner case 2
        if sum(nums) < abs(target):
            return 0
        pos = (sum(nums) + target) // 2

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

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

Complexity Analysis

• Time complexity: O(M*N)
• Space complexity: O(N)

[JiangyanLiNEU]

Idea

• memorize , today's problem can be converted to the same problem as yesterday's

  Python

  class Solution(object):
  def findTargetSumWays(self, nums, target):memo = {}
      def update(index, target):
          if index == len(nums)-1:
              if target == 0:
                  memo[(index, target)] = 2 if nums[index] == 0 else 1
              else:
                  memo[(index, target)] = 1 if nums[index]==target else 0
          else:
              newTarget = target-nums[index]
              update(index+1, newTarget) if (index+1, newTarget) not in memo else None
              update(index+1, target) if (index+1, target) not in memo else None
              memo[(index, target)] = memo[(index+1, newTarget)] + memo[(index+1, target)]
      summ = sum(nums)
      if summ < target:
          return 0
      else:
          minus = summ-target
          if minus%2 != 0:
              return 0
          newTarget = minus//2
          update(0, newTarget)
          return memo[(0, newTarget)]

[heyqz]

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        def helper(index, cur_sum):
            if index == len(nums):
                if cur_sum == target:
                    return 1
                else: 
                    return 0
            return helper(index + 1, cur_sum + nums[index]) + helper(index + 1, cur_sum - nums[index])

        return helper(0, 0)

[tongxw]

思路

感觉背包问题最难的是如何抽象成背包模型。。总是想不起来。 用暴力dfs解决的，就是想象成二叉树（左子树+，右子树-），最后统计叶子节点上target == 0的个数。

代码

class Solution {
  public int findTargetSumWays(int[] nums, int target) {                                              
    return dfs(nums, nums.length, target);
  }

  private int dfs(int[] nums, int n, int target) {
    if (n == 0) {
      return target == 0 ? 1 : 0;
    }

    return dfs(nums, n - 1, target + nums[n-1]) + dfs(nums, n -1, target - nums[n-1]);
  }
}

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

[zhangzz2015]

思路

• 先考虑top down。定义dp 函数 dp(x, y) 在nums[0: x] 范围里找到target 为 y 组合数，因为在选择nums[x] 可选择 +num[x] 或者 -nums[x]，因此 递推关系为 dp(x, y) = dp(x-1, y+nums[x]) + dp(x-1, y-nums[x])
• 方法1， 采用dfs + mem 方法，该方法通用性强，可处理更多的情况，甚至还可以考虑乘法甚至是负的nums等，时间复杂度为O(2^n) n 为nums的size，空间复杂度为O(m)，m 为所有组合最大 和最小的范围。
• 方法2， 可采用dp，因为nums都是正数，因此可定义最大的范围[-sum(nums) sum(nums)] 。建立二维table。时间复杂度为O( 2m n) m为最所有nums求和，n 为nums size。空间复杂度为O(2mn)，
• 方法3，因为dp 函数之和上一次的状态相关，可压缩空间复杂度到O(2*m)

关键点

代码

• 语言支持：C++

C++ Code:

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

        ///  
        ///    i  target  j from nums[0 : j] and you can find x 
        ///  dp[i][j] =  dp[i- nums[j]][j-1] + dp[i + nums[j]][j-1]

        unordered_map<int, unordered_map<int,int>> mem; 
        return dfs(nums, target, nums.size()-1, mem); 

    }

    int dfs(vector<int>& nums, int target, int index,  unordered_map<int, unordered_map<int,int>>& mem)
    {
        if(index<0&& target !=0 )
            return 0; 
        if(target ==0 && index<0)
            return 1; 

        if(mem.find(target) != mem.end() && mem[target].find(index) != mem[target].end())
            return mem[target][index]; 

        int totalSum= 0; 
        totalSum += dfs(nums, target - nums[index], index-1, mem); 
        totalSum += dfs(nums, target + nums[index], index-1, mem); 

        mem[target][index] = totalSum; 
        return totalSum ; 
    }
};

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

        ///  
        ///    i  target  j from nums[0 : j] and you can find x 
        ///  dp[i][j] =  dp[i- nums[j]][j-1] + dp[i + nums[j]][j-1]

        int totalSum =0; 
        for(int i=0; i< nums.size(); i++)
            totalSum +=nums[i]; 
        if(target >totalSum || target <-totalSum)
            return 0; 

        vector<vector<int>> dpTable(nums.size()+1, vector<int>(totalSum*2+1,0)); 
        dpTable[0][totalSum] = 1; 
        for(int i = 1; i<=nums.size(); i++)
        {
            for(int j = - totalSum; j <=totalSum; j++)
            {
                if(j-nums[i-1]>=-totalSum && j-nums[i-1]<=totalSum)
                 dpTable[i][j+totalSum] += dpTable[i-1][j - nums[i-1] +totalSum]; 
                if(j+nums[i-1]>=-totalSum && j+nums[i-1]<=totalSum)
                 dpTable[i][j+totalSum] += dpTable[i-1][j+nums[i-1]+totalSum];       
            }
        }

        return dpTable[nums.size()][target+totalSum]; 

    }
};

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

        ///  
        ///    i  target  j from nums[0 : j] and you can find x 
        ///  dp[i][j] =  dp[i- nums[j]][j-1] + dp[i + nums[j]][j-1]

        int totalSum =0; 
        for(int i=0; i< nums.size(); i++)
            totalSum +=nums[i]; 
        if(target >totalSum || target <-totalSum)
            return 0; 

        vector<int> dpTable1(totalSum*2+1,0); 
        vector<int> dpTable2(totalSum*2+1,0);  
        dpTable1[totalSum] = 1; 
        int* prev = &dpTable1[0];        
        int* current = &dpTable2[0]; 
        for(int i = 1; i<=nums.size(); i++)
        {
            for(int j = - totalSum; j <=totalSum; j++)
            {
                current[j+totalSum] =0;
                if(j-nums[i-1]>=-totalSum && j-nums[i-1]<=totalSum)
                 current[j+totalSum] += prev[j - nums[i-1] +totalSum]; 
                if(j+nums[i-1]>=-totalSum && j+nums[i-1]<=totalSum)
                 current[j+totalSum] += prev[j + nums[i-1]+totalSum];       
            }

            swap(current, prev); 
        }

        return prev[target+totalSum]; 

    }
};

[littlemoon-zh]

Top down memo solution:

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        memo = {} 
        def dfs(i, cur):

            if (i, cur) in memo:
                return memo[i, cur]

            if i == len(nums):
                if cur == target:
                    return 1
                return 0

            res = dfs(i + 1, cur + nums[i]) + dfs(i + 1, cur - nums[i])
            memo[i, cur] = res
            return res

        return dfs(0, 0)

[wangzehan123]

题目地址(494. 目标和)

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

题目描述

给你一个整数数组 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

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：Java

Java Code:

public class Solution {
    int count = 0;
    public int findTargetSumWays(int[] nums, int S) {
        calculate(nums, 0, 0, S);
        return count;
    }
    public void calculate(int[] nums, int i, int sum, int S) {
        if (i == nums.length) {
            if (sum == S)
                count++;
        } else {
            calculate(nums, i + 1, sum + nums[i], S);
            calculate(nums, i + 1, sum - nums[i], S);
        }
    }
}

复杂度分析

令 n 为数组长度。

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

[st2yang]

思路

• dp

代码

• python

  class Solution:
  def findTargetSumWays(self, nums: List[int], target: int) -> int:
      @lru_cache(None)
      def backtracking(i, value):
          if i == len(nums):
              return 1 if value == 0 else 0
  
          return backtracking(i + 1, value + nums[i]) + backtracking(i + 1, value - nums[i])
  
      return backtracking(0, target)

复杂度

• 时间: O(n * sum)
• 空间: O(n * sum)

[florenzliu]

Explanation

• math problem (since nums is a list of non-negative numbers):
  • positive + negative = target
  • positive - negative = total
  • => positive = (target+total)/2
• knapsack problem using 1-D dp: the number of knapsacks is positive
  • dp[i] = dp[i-nums[j]]

Python

class Solution:
    # Approach 1: backtracking
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        @lru_cache(None)
        def backtracking(n, currSum):
            if n < 0:
                if currSum == 0: 
                    return 1
                return 0
            return backtracking(n-1, currSum - nums[n]) + backtracking(n-1, currSum + nums[n])

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

    # Approach 2: bottom up dynamic programming (knapsack problem)
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        if (target + sum(nums)) % 2 or sum(nums) < abs(target):
            return 0
        positive = (target + sum(nums)) // 2
        dp = [0 for i in range(positive+1)]
        dp[0] = 1

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

Complexity:

• Time Complexity: O(mn) where m is (total+target)//2 and n is the length of the nums list
• Space Complexity: O(m)

[zol013]

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]

[skinnyh]

Note

• Original thought: Let dp[i][j] mean the number of expressions to make a sum of j with first i elements. So dp[i][j] = dp[i-1][j + nums[i]] + dp[i - 1][j - nums[i]]. Because there can be negatives so j's range will be in [-sum, sum]. We need to shift it by sum to work with the array index.
• This can also be solved by converting it to a knapsack problem. We know positive+negative=targeand positive−negative=total Sopositive=(target+total)/2 This becomes a 01 knapsack problem to select numbers with positive sign to make a sum of (target + total) / 2 So we can get dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]] We can use 1D array to compress space.

Solution

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if target > total or target < -total:
            return 0
        t = total + target
        if t % 2 != 0:
            return 0
        t //= 2
        # dp[i][j] means the number of expressions to make sum of j for the first i elements
        dp = [0] * (t + 1)
        dp[0] = 1
        for i in range(len(nums)):
            for j in range(t, -1, -1):
                if j >= nums[i]:
                    dp[j] += dp[j - nums[i]]
        return dp[t]

Time complexity: O(M * N) M=(total+target)/2, N=len(nums)

Space complexity: O(M)

[pophy]

思路1 DFS

Java Code

class Solution {
    int result = 0;

    public int findTargetSumWays(int[] nums, int S) {
        if (nums == null || nums.length == 0) return result;
        helper(nums, S, 0, 0);
        return result;
    }

    public void helper(int[] nums, int target, int pos, long eval){
        if (pos == nums.length) {
            if (target == eval) result++;
            return;
        }
        helper(nums, target, pos + 1, eval + nums[pos]);
        helper(nums, target, pos + 1, eval - nums[pos]);
    }
}

时间&空间

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

思路2 - DP

• 题目给出条件所有数之和 sum < 1000 因此考虑类似knapsack类型DP
• 用map代替数组 避免出现下标为负数的问题
• 每新加一个数 类似order traverse

Java Code

    public int findTargetSumWays(int[] nums, int target) {
        Map<Integer, Integer> dp = new HashMap();
        dp.put(0, 1);
        for (int num : nums) {
            Map<Integer, Integer> dp2 = new HashMap();
            for (int tempSum : dp.keySet()) {
                int key1 = tempSum + num;
                dp2.put(key1, dp2.getOrDefault(key1, 0) + dp.get(tempSum));
                int key2 = tempSum - num;
                dp2.put(key2, dp2.getOrDefault(key2, 0) + dp.get(tempSum));
            }
            dp = dp2;
        }
        return dp.getOrDefault(target, 0);
    }

时间&空间

• 时间 O(n * k)
• 空间 O(2 * k) k < 1000

[yan0327]

思路： 本题是0-1背包组合问题。虽然题目是目标和，即可以考虑给数组的各位加+或-， 但是我们可以把他转变成一个求正数和的背包问题。我们令x为数组的正数和，y为数组里负数的和。 此时满足x+y = target(两数之差) ， x-y = sum（数组之和） =》运算可以得到x = (target+sum)/2 因此，我们只要找满足x大小的整数和的组合即可 于是用背包问题的组合方式，生成一个x+1的dp数组，外层遍历物品重量，内层从背包容量依次减少到该物品重量。 最终找到答案。 注意一个特殊的测试用例，存在x＜0的情况，因此在这里加入了一个判断语言过滤掉

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

时间复杂度：O（M*N）其中M为(sum+target)/2 空间复杂度：O（M）

[shawncvv]

思路

背包

代码

JavaScript Code

var findTargetSumWays = function (nums) {
  const sum = nums.reduce((a, b) => a + b, 0);
  let t = sum + target;
  if (t % 2) 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(M*N）其中M为(sum+target)/2
• 空间复杂度：O(M)

[Shinnost]

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

[ForLittleBeauty]

思路

---

通过

• A+B = Sum
• A-B = Target

把nums分割成两个subset，那么其中一个subset的需要满足值，就是

A = (Sum+Target)/2

这样就转化成了昨天的那道题。

---

代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:

        if sum(nums)%2!=0:
            return False
        else:
            target = sum(nums)//2

        dp = [True if i==nums[0] else False for i in range(target+1)]
        dp[0] = True

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

        return dp[-1]

---

时间复杂度: O(mn)

空间复杂度: O(n)

其中m为数组长度,n与sum和target有关

[okbug]

class Solution {
public:
    int findTargetSumWays(vector<int>& a, int S) {
        if (S < -1000 || S > 1000) return 0;
        int n = a.size(), Offset = 1000;
        vector<vector<int>> f(n + 1, vector<int>(2001));
        f[0][Offset] = 1;
        for (int i = 1; i <= n; i ++ )
            for (int j = -1000; j <= 1000; j ++ ) {
                if (j - a[i - 1] >= -1000)
                    f[i][j + Offset] += f[i - 1][j - a[i - 1] + Offset];
                if (j + a[i - 1] <= 1000)
                    f[i][j + Offset] += f[i - 1][j + a[i - 1] + Offset];
            }
        return f[n][S + Offset];
    }
};

[chun1hao]

var findTargetSumWays = function (nums, target) {
  let ans = 0;
  let len = nums.length;
  let helper = (idx, sum) => {
    if (idx > len) return;
    if (idx == len && sum === target) return ans++;
    helper(idx + 1, sum + nums[idx]);
    helper(idx + 1, sum - nums[idx]);
  };
  helper(0, 0);
  return ans;
};

[ninghuang456]

public class Solution {
    public int findTargetSumWays(int[] nums, int s) {
        int sum = 0; 
        for(int i: nums) sum+=i;
        if(s>sum || s<-sum) return 0;
        int[] dp = new int[2*sum+1];
        dp[0+sum] = 1;
        for(int i = 0; i<nums.length; i++){
            int[] next = new int[2*sum+1];
            for(int k = 0; k<2*sum+1; k++){
                if(dp[k]!=0){
                    next[k + nums[i]] += dp[k];
                    next[k - nums[i]] += dp[k];
                }
            }
            dp = next;
        }
        return dp[sum+s];
    }
}

[thinkfurther]

思路

使用递归，每次深度加1，然后分别是正数或者负数。

代码

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
       @lru_cache(None)
       def f(i, cur_sum):
           if i == len(nums):
               if target == cur_sum:
                   return 1
               return 0

           return f(i + 1, cur_sum + nums[i]) + f(i + 1, cur_sum - nums[i])

       return f(0, 0)

[Moin-Jer]

思路

---

动态规划

代码

---

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(n*(sum−target))

[liuyangqiQAQ]

传统的dp 和昨天的思路很像

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        int n = (sum - target);
        //也就是说某些值相加 * 2 得到n时那么这个方案就可以选
        if(n % 2 != 0 || n < 0) return 0;
        int m = n / 2;
        int[][] dp = new int[nums.length + 1][m + 1];
        //如果m为正整数那么我们至少有一个方案，所以
        dp[0][0] = 1;
        for (int i = 1; i < nums.length + 1; i++) {
            //当前的值选与不选？选
            int num = nums[i - 1];
            for (int j = 0; j < m + 1; j++) {
                dp[i][j] = dp[i - 1][j];
                if(j >= num) {
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[nums.length][m];
    }
}

时间复杂度: O(N)(sum(nums) - target) N为数组长度 sum(nums)为数组之和

空间复杂度: O(N)(sum(nums) - target) N为数组长度 sum(nums)为数组之和

和昨天一样可以用一维数组代替前一项数据

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        int n = (sum - target);
        //也就是说某些值相加 * 2 得到n时那么这个方案就可以选
        if(n % 2 != 0 || n < 0) return 0;
        int m = n / 2;
        int[] dp = new int[m + 1];
        //如果m为正整数那么我们至少有一个方案，所以
        dp[0] = 1;
        for (int i = 1; i < nums.length + 1; i++) {
            //当前的值选与不选？选
            int num = nums[i - 1];
            int[] tempDp = new int[m + 1];
            for (int j = 0; j < m + 1; j++) {
                tempDp[j] = dp[j];
                if(j >= num) {
                    tempDp[j] += dp[j - num];
                }
            }
            dp = tempDp;
        }
        return dp[m];
    }
}

时间复杂度: O(N)(sum(nums) - target) N为数组长度 sum(nums)为数组之和

空间复杂度: O(sum(nums))

[ZacheryCao]

Idea:

DP. For nums[i], dp[i] the total ways to get sum equals to j. The transit function will be dp[j] = dp[j+nums[i]] + dp[j-nums[i]].

Code:

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if total < target or -total > target:
            return 0
        dp = {}
        seen = set()
        seen.add(nums[0])
        seen.add(-nums[0])
        if nums[0]:
            dp[nums[0]] = 1
            dp[-nums[0]] = 1
        else:
            dp[0] = 2
        for i in range(1,len(nums)):
            cur = set()
            cur_dp = {}
            while seen:
                j = seen.pop()
                if j + nums[i] not in cur_dp:
                    cur_dp[j+nums[i]] = dp[j]
                else:
                    cur_dp[j+nums[i]] += dp[j]
                cur.add(j + nums[i])
                if j - nums[i] not in cur_dp:
                    cur_dp[j-nums[i]] = dp[j]
                else:
                    cur_dp[j-nums[i]] += dp[j]
                cur.add(j-nums[i])
            seen = cur
            dp = cur_dp
        return dp[target] if target in dp else 0

Complexity:

Time: O(n * total). total = sum(nums) Space: O(total)

[machuangmr]

题目494. 目标和

思路

• 回溯法，参考官方题解

  代码

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

  复杂度

• 时间复杂度 O(2^n)
• 空间复杂度 O(n)

[shixinlovey1314]

Title:494. Target Sum

Question Reference LeetCode

Solution

At each index i, the number of sums that it can contribute only depends on the number of sums we had at index i - 1. In order to find the number of ways to get a sum, we could use a map at each index to count the number of sums.

Code

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0)
            return 0;

        vector<map<int,int>> sumDp(n);
        sumDp[0][nums[0]] += 1;
        sumDp[0][-nums[0]] += 1;

        for (int i = 1; i < nums.size(); i++) {
            for (auto it : sumDp[i-1]) {
                sumDp[i][it.first + nums[i]] += it.second;
                sumDp[i][it.first - nums[i]] += it.second;
            }
        }

        return sumDp[n-1][target];
    }
};

Complexity

Time Complexity and Explanation

O(n* 2^n)

Space Complexity and Explanation

O(n* 2^n)

[shamworld]

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

[JK1452470209]

思路

dp 每个元素只能用一次

代码

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if (sum < Math.abs(target))
            return 0;
        if (((sum + target) & 1) == 1){
            return 0;
        }
        int mid = (sum + target) / 2;
        int[] dp = new int[mid + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = mid; j >= nums[i]; j--) {
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        return dp[mid];
    }
}

复杂度

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

空间复杂度：O(N)

[Serena9]

代码

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]

[QiZhongdd]

var findTargetSumWays = function (nums) {
  const sum = nums.reduce((a, b) => a + b, 0);
  let t = sum + target;
  if (t % 2) 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];
};

[ai2095]

494. Target Sum

https://leetcode.com/problems/partition-equal-subset-sum/

Topics

• DP

思路

It's like a 0-1 backpack problem.

代码 Python

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        dic = defaultdict(int)
        if nums[0] != 0:     
            dic[nums[0]] = 1
            dic[-nums[0]] = 1
        else:
            dic[nums[0]] = 2

        for i in range(1, len(nums)):
            tdic = defaultdict(int)
            for d in dic:

                tdic[d + nums[i]] = tdic[d + nums[i]] + dic[d]
                tdic[d - nums[i]] = tdic[d - nums[i]] + dic[d]
            dic = tdic
        return dic[target]

复杂度分析

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

[ychen8777]

思路

寻找 正项 - 负项 = target \ => 总和 - 负项 - 负项 = target \ => 负项 = (总和 - target) / 2 \ 转化成在数组 nums 中选取若干元素，使得这些元素之和等于 负项

代码

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 negSum =diff / 2;
        int[] dp = new int[negSum+1];
        dp[0] = 1;

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

        return dp[negSum];

    }
}

复杂度

时间: O(n * (sum(nums) - target) \ 空间: O (sum(nums) - target)

[ghost]

题目

494. Target Sum

思路

DP or DFS with memory

代码

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        dp = collections.defaultdict(int)
        dp[0] = 1

        for i in range(n):
            temp = collections.defaultdict(int)
            for k in dp:
                v = dp[k]
                temp[k + nums[i]] += v
                temp[k - nums[i]] += v
            dp = temp

        return dp[target]

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

        def helper(start, curr):
            if start == len(nums):
                return curr == S
            if (start,curr) in memo:
                return memo[(start,curr)]

            l = helper(start+1,curr+nums[start])
            r = helper(start+1,curr-nums[start])
            memo[(start,curr)] = l+r

            return l+r

        memo = {}
        return helper(0,0)

复杂度

Space: O(n) Time: O(s*n)

[Francis-xsc]

思路

动态规划背包问题

代码

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

};

复杂度分析

• 时间复杂度：O(N*(sum-target))，其中 N 为数组长度。
• 空间复杂度：O(sum-target)

[hwpanda]

var findTargetSumWays = function (nums, target) {
    const n = nums.length;
    const sum = nums.reduce((sum, x) => sum + x);
    if (sum < Math.abs(target)) return 0;
    if ((sum - target) % 2 === 1) return 0;

    const range = sum * 2 + 1;
    const dp = new Array(n).fill().map((x) => new Array(range).fill(0));

    for (let j = 0; j <= range; j++) {
        if (nums[0] === j - sum || -nums[0] === j - sum) {
            // console.log(j)
            if (nums[0] === 0) {
                dp[0][j] = 2;
            } else {
                dp[0][j] = 1;
            }
        }
    }

    for (let i = 1; i < n; i++) {
        for (let j = 0; j < range; j++) {
            if (j - nums[i] >= 0) {
                dp[i][j] += dp[i - 1][j - nums[i]];
            }
            if (j + nums[i] < range) {
                dp[i][j] += dp[i - 1][j + nums[i]];
            }
        }
    }
    // console.log(dp)
    return dp[n - 1][target + sum];
};