494. Target Sum

Problem ::  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.


Time Complexity :: O(N^2)

Space Complexity :: O(N)


Code ::
#pragma gcc optimize("03")
auto init = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 'c';
}();
class Solution {
    int solve(vector<int>& nums, int &target , int i , int sum ,  vector<vector<int>>&dp){
        if( i == nums.size()){
            if(sum == target)return 1;
            return 0;
        }
        if(dp[i][sum+1000]!=-1)return dp[i][sum+1000];
        int take =  solve(nums , target, i+1 , sum+nums[i] , dp);
        int notake = solve(nums , target, i+1 , sum-nums[i] , dp);
        return dp[i][sum+1000] = take + notake;
    }
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        vector<vector<int>>dp(nums.size()+1 , vector<int>(2002,-1));
       return  solve(nums , target , 0 , 0 , dp);
         
    }
};

// i + 1000 , 1000-i