494. 目标和

目标和

• 难度: medium
• 原始链接: https://leetcode.cn/problems/target-sum
• 标签: 深度优先遍历

解法一: 深度优先遍历

go

func findTargetSumWays(nums []int, target int) int {
  // f(i) = nums[i] + f(i - 1)
  // f(i) = -nums[i] + f(i - 1)
  ans := 0
  var dfs func(int, int)
  dfs = func(i, cur int) {
    if i < 0 {
      if cur == 0 {
        ans++
      }
      return
    }
    dfs(i-1, cur+nums[i])
    dfs(i-1, cur-nums[i])
  }
  dfs(len(nums)-1, target)
  return ans
}