Question

494. Target Sum

中文文档

Description

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

 

Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 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

Example 2:

Input: nums = [1], target = 1
Output: 1

 

Constraints:

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

Solutions

Solution 1

class Solution:
  def findTargetSumWays(self, nums: List[int], target: int) -> int:
    s = sum(nums)
    if s < target or (s - target) % 2 != 0:
      return 0
    m, n = len(nums), (s - target) // 2
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = 1
    for i in range(1, m + 1):
      for j in range(n + 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[-1][-1]

class Solution {
  public int findTargetSumWays(int[] nums, int target) {
    int s = 0;
    for (int v : nums) {
      s += v;
    }
    if (s < target || (s - target) % 2 != 0) {
      return 0;
    }
    int m = nums.length;
    int n = (s - target) / 2;
    int[][] dp = new int[m + 1][n + 1];
    dp[0][0] = 1;
    for (int i = 1; i <= m; ++i) {
      for (int j = 0; j <= n; ++j) {
        dp[i][j] = dp[i - 1][j];
        if (nums[i - 1] <= j) {
          dp[i][j] += dp[i - 1][j - nums[i - 1]];
        }
      }
    }
    return dp[m][n];
  }
}

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

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

impl Solution {
  #[allow(dead_code)]
  pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
    let mut sum = 0;
    for e in &nums {
      sum += *e;
    }

    // -x + (sum - x) = target <-> -2 * x + sum = target <-> 2 * x = sum - target
    if sum < target || (sum - target) % 2 != 0 {
      // There is no way to get any expression in this case
      return 0;
    }
    let n = nums.len();
    let m = (sum - target) / 2;

    let mut dp: Vec<Vec<i32>> = vec![vec![0; m as usize + 1]; n + 1];

    // Initialize the dp vector
    dp[0][0] = 1;

    // Begin the actual dp phase
    for i in 1..=n {
      for j in 0..=m as usize {
        // nums[i - 1] is not included
        dp[i][j] = dp[i - 1][j];
        if nums[i - 1] <= (j as i32) {
          // nums[i - 1] is included
          dp[i][j] += dp[i - 1][j - (nums[i - 1] as usize)];
        }
      }
    }

    dp[n][m as usize]
  }
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function (nums, target) {
  let s = 0;
  for (let v of nums) {
    s += v;
  }
  if (s < target || (s - target) % 2 != 0) {
    return 0;
  }
  const m = nums.length;
  const n = (s - target) / 2;
  let dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  for (let i = 1; i <= m; ++i) {
    for (let j = n; j >= nums[i - 1]; --j) {
      dp[j] += dp[j - nums[i - 1]];
    }
  }
  return dp[n];
};

Solution 2

class Solution:
  def findTargetSumWays(self, nums: List[int], target: int) -> int:
    s = sum(nums)
    if s < target or (s - target) % 2 != 0:
      return 0
    n = (s - target) // 2
    dp = [0] * (n + 1)
    dp[0] = 1
    for v in nums:
      for j in range(n, v - 1, -1):
        dp[j] += dp[j - v]
    return dp[-1]

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

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

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

impl Solution {
  #[allow(dead_code)]
  pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
    let mut sum = 0;
    for e in &nums {
      sum += *e;
    }

    if sum < target || (sum - target) % 2 != 0 {
      // Just directly return
      return 0;
    }

    let n = ((sum - target) / 2) as usize;
    let mut dp: Vec<i32> = vec![0; n + 1];

    // Initialize the dp vector
    dp[0] = 1;

    // Begin the actual dp phase
    for e in &nums {
      for i in (*e as usize..=n).rev() {
        dp[i] += dp[i - (*e as usize)];
      }
    }

    dp[n]
  }
}

Solution 3

class Solution:
  def findTargetSumWays(self, nums: List[int], target: int) -> int:
    @cache
    def dfs(i, t):
      if i == n:
        if t == target:
          return 1
        return 0
      return dfs(i + 1, t + nums[i]) + dfs(i + 1, t - nums[i])

    ans, n = 0, len(nums)
    return dfs(0, 0)