Untitled

class Solution {
    int count = 0;
    vector<string> v;
public:
    void solve(string s, int ind, int sum, vector<vector<int>>& dp, vector<int>& nums, int k){
        if(ind == nums.size()) {v.push_back(s); return;}

        // 1st Case: Positive
        int modifiedSum = sum + nums[ind];
        s += ("+" + to_string(nums[ind]));

        // if(modifiedSum == k){
        //     count++;
        // }
        if(dp[ind][modifiedSum] == 0){
            count++;
        }
        else{
            dp[ind][modifiedSum]++;
        }
        
        solve(s, ind + 1, modifiedSum, dp, nums, k);

        int j = s.size()-1;

        while(j >= 0 && (s[j] != '-' && s[j] != '+')){
            j--;
        }
        s = s.substr(0, j);

        // 2nd Case: Negative
        modifiedSum = sum - nums[ind];
        s += ("-" + to_string(nums[ind]));

        // if(modifiedSum == k){
        //     count++;
        // }
        if(dp[ind][modifiedSum] != 0){
            count++;
        }
        else{
            dp[ind][modifiedSum]++;
        }

        solve(s, ind + 1, modifiedSum, dp, nums, k);

        j = s.size()-1;

        while(j >= 0 && (s[j] != '-' && s[j] != '+')){
            j--;
        }
        s = s.substr(0, j);

    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int posSum = 0;

        for(auto x : nums){
            posSum += x;
        }

        vector<vector<int>> dp(nums.size() + 1, vector<int> (2*posSum+1, 0));

        solve("", 0, 0, dp, nums, target);
        // for(auto x : v){
        //     cout<<x<<endl;
        // }

        return count;
    }
};