leetcode_rust/
target_sum.rs

1#![allow(dead_code)]
2#![allow(unused_variables)]
3#![allow(unused_imports)]
4
5// dfs: O(2^n)
6pub fn find_target_sum_ways(nums: Vec<i32>, s: i32) -> i32 {
7    _find_target_sum_ways(&nums, 0, s, 0)
8}
9
10fn _find_target_sum_ways(nums: &Vec<i32>, index: usize, s: i32, sum: i32) -> i32 {
11    let mut res = 0;
12    if index == nums.len() {
13        if sum == s {
14            res += 1;
15            return res;
16        } else {
17            return res;
18        }
19    } else {
20        res += _find_target_sum_ways(&nums, index + 1, s, sum + nums[index]);
21        res += _find_target_sum_ways(&nums, index + 1, s, sum - nums[index]);
22        res
23    }
24}
25
26/// analysis and dp
27/// sum(P) - sum(N) = target
28/// sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
29/// 2 * sum(P) = target + sum(nums)
30/// so, if target + sum(nums) is not even, return 0,
31/// else get sum(P) ==  (target + sum(nums))/2
32// todo
33pub fn find_target_sum_ways2(nums: Vec<i32>, s: i32) -> i32 {
34    unimplemented!()
35}
36
37#[cfg(test)]
38mod tests {
39    use super::*;
40
41    #[test]
42    fn test1() {
43        assert_eq!(find_target_sum_ways(vec![1, 1, 1, 1, 1], 3), 5);
44    }
45}
leetcode_rust/target_sum.rs

leetcode_rust/
target_sum.rs
