1
class Solution { // YAA
2
 public:
3
  int solve(vector<int> &nums, int target, int idx, unordered_map<string, int> &dp) {
4
    if (idx == nums.size()) {
5
      if (target == 0) {
6
        return 1;
7
      }
8
      return 0;
9
    }
10
    string key = to_string(idx) + " " + to_string(target);
11
    if (dp.find(key) != dp.end()) {
12
      return dp[key];
13
    }
14
    // +
15
    int x = solve(nums, target - nums[idx], idx + 1, dp);
16
    // -
17
    int y = solve(nums, target + nums[idx], idx + 1, dp);
18
    // sum
19
    return dp[key] = x + y;
20
  }
21
  int findTargetSumWays(vector<int> &nums, int target) {
22
    unordered_map<string, int> dp;
23
    return solve(nums, target, 0, dp);
24
  }
25
};