## 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.