494. Target Sum

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols ‘+’ and ‘-‘ before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a ‘+’ before 2 and a ‘-‘ before 1 and concatenate them to build the expression “+2-1”.

Return the number of different expressions that you can build, which evaluates to target.

class Solution {
    unordered_map<int, int> m[20];
public:
    int findTargetSumWays(vector<int>& nums, int& target, int c = 0, int i = 0) {
        if(i == nums.size()) {
            return c == target;
        }
        if(m[i].count(c)) return m[i][c];
        return m[i][c] = findTargetSumWays(nums, target, c + nums[i], i + 1) + findTargetSumWays(nums, target, c - nums[i], i + 1);
    }
};