题目

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

注意：本题与主站 494 题相同：

解题思路分析

1、递归；时间复杂度O(2^n)，空间复杂度O(n)

func findTargetSumWays(nums []int, S int) int {
   if len(nums) == 0 {
      return 0
   }
   if len(nums) == 1 {
      if nums[0] == 0 && S == 0 {
         return 2
      }
      if nums[0] == S || nums[0] == -S {
         return 1
      }
   }
   value := nums[0]
   nums = nums[1:]
   return findTargetSumWays(nums, S-value) + findTargetSumWays(nums, S+value)
}

2、动态规划；时间复杂度O(2^n)，空间复杂度O(n)

func findTargetSumWays(nums []int, S int) int {
   dp := make(map[int]int)
   dp[nums[0]]++
   dp[-nums[0]]++
   for i := 1; i < len(nums); i++ {
      temp := make(map[int]int)
      for k, v := range dp {
         temp[k-nums[i]] = temp[k-nums[i]] + v
         temp[k+nums[i]] = temp[k+nums[i]] + v
      }
      dp = temp
   }
   return dp[S]
}

3、回溯；时间复杂度O(2^n)，空间复杂度O(n)

var res int

func findTargetSumWays(nums []int, S int) int {
   res = 0
   dfs(nums, 0, S)
   return res
}

func dfs(nums []int, index int, target int) {
   if index == len(nums) {
      if target == 0 {
         res++
      }
      return
   }
   dfs(nums, index+1, target+nums[index])
   dfs(nums, index+1, target-nums[index])
}

4、动态规划；时间复杂度O(n^2)，空间复杂度O(n)

func findTargetSumWays(nums []int, S int) int {
   sum := 0
   // 非负整数数组
   for i := 0; i < len(nums); i++ {
      sum = sum + nums[i]
   }
   if sum < int(math.Abs(float64(S))) || (sum+S)%2 == 1 {
      return 0
   }
   // 一个正数x,一个负数背包y => x+y=sum, x-y=S => (sum+S)/2=x
   target := (sum + S) / 2
   dp := make([]int, target+1)
   dp[0] = 1
   for i := 1; i <= len(nums); i++ {
      // 从后往前，避免覆盖
      for j := target; j >= 0; j-- {
         if j >= nums[i-1] {
            // 背包足够大，都选
            dp[j] = dp[j] + dp[j-nums[i-1]]
         } else {
            // 容量不够，不选
            dp[j] = dp[j]
         }
      }
   }
   return dp[target]
}

5、动态规划；时间复杂度O(n^2)，空间复杂度O(n^2)

func findTargetSumWays(nums []int, S int) int {
   sum := 0
   // 非负整数数组
   for i := 0; i < len(nums); i++ {
      sum = sum + nums[i]
   }
   if sum < int(math.Abs(float64(S))) || (sum+S)%2 == 1 {
      return 0
   }
   // 一个正数x,一个负数背包y => x+y=sum, x-y=S => (sum+S)/2=x
   target := (sum + S) / 2
   // 在前i个物品中选择，若当前背包的容量为j，则最多有x种方法可以恰好装满背包。
   dp := make([][]int, len(nums)+1)
   for i := 0; i <= len(nums); i++ {
      dp[i] = make([]int, target+1)
      dp[i][0] = 1 // 容量为0， 只有都不选
   }
   for i := 1; i <= len(nums); i++ {
      for j := 0; j <= target; 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[len(nums)][target]
}

总结

Medium题目，题目同leetcode 494.目标和