impl Solution {
    fn dfs(nums: &Vec<i32>, index: i32, sum: i32, s: i32, ans: &mut i32) {
        if index == nums.len() as i32 {
            if sum == s {
                *ans += 1;
            }
            return;
        }

        Self::dfs(nums, index + 1, sum + nums[index as usize], s, ans);
        Self::dfs(nums, index + 1, sum - nums[index as usize], s, ans);
    }
    pub fn find_target_sum_ways(nums: Vec<i32>, s: i32) -> i32 {
        let mut ans = 0;
        Self::dfs(&nums, 0, 0, s, &mut ans);
        return ans;
    }
}

use std::collections::{HashMap, VecDeque};
impl Solution {
    pub fn next_greater_element(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let mut ans = vec![];
        let mut stack: Vec<i32> = vec![];
        let mut m = HashMap::new();

        for num in nums2 {
            while !stack.is_empty() {
                let cur = stack.last().unwrap().clone();
                if cur >= num {
                    break;
                }

                m.entry(cur).or_insert(0);
                *m.get_mut(&cur).unwrap() = num;
                stack.pop();
            }
            stack.push(num);
        }

        for num in nums1 {
            if m.contains_key(&num) {
                ans.push(*m.get(&num).unwrap());
            } else {
                ans.push(-1);
            }
        }
        return ans;
    }
}

impl Solution {
    pub fn next_greater_elements(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut ans = vec![-1; n];
        let mut stack: Vec<usize> = vec![];

        for i in 0..2 * n {
            let num = nums[i % n];
            while !stack.is_empty() {
                let top = stack.last().unwrap().clone();
                if nums[top] >= num {
                    break;
                }
                ans[top] = num;
                stack.pop();
            }
            if i < n {
                stack.push(i);
            }
        }

        return ans;
    }
}