Welcome to Subscribe On Youtube

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

Dynamic programming.

It is similar to the 0-1 Knapsack problem, except that the index may appear negative, which requires special handling.

• Java
• C++
• Python
• Go
• Javascript
• RenderScript

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

• 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]
  
  

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

• /**
   * @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];
  };
  
  

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

All Problems

All Solutions