494. Target Sum

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-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

There are 5 ways to assign symbols to make the sum of nums be target 3.

 

Constraints:

  • The length of the given array is positive and will not exceed 20.
  • The sum of elements in the given array will not exceed 1000.
  • Your output answer is guaranteed to be fitted in a 32-bit integer.

Rust Solution

struct Solution;

use std::collections::HashMap;

impl Solution {
    fn find_target_sum_ways(nums: Vec<i32>, s: i32) -> i32 {
        let n = nums.len();
        let mut memo: HashMap<(usize, i32), i32> = HashMap::new();
        Self::dp(n, s, &mut memo, &nums, n)
    }

    fn dp(
        end: usize,
        sum: i32,
        memo: &mut HashMap<(usize, i32), i32>,
        nums: &[i32],
        n: usize,
    ) -> i32 {
        if end == 0 {
            if sum == 0 {
                1
            } else {
                0
            }
        } else {
            if let Some(&res) = memo.get(&(end, sum)) {
                return res;
            }
            let a = Self::dp(end - 1, sum + nums[end - 1], memo, nums, n);
            let b = Self::dp(end - 1, sum - nums[end - 1], memo, nums, n);
            let res = a + b;
            memo.insert((end, sum), res);
            res
        }
    }
}

#[test]
fn test() {
    let nums = vec![1, 1, 1, 1, 1];
    let s = 3;
    let res = 5;
    assert_eq!(Solution::find_target_sum_ways(nums, s), res);
}

Having problems with this solution? Click here to submit an issue on github.