class Solution {
public:
    int f(int index,int target,vector<int> &nums,vector<vector<int>> &dp) {

      //  if(target<0) return 0;

if(index==0) {
    if(nums[index]==target && target==0) return 2;
    if(nums[index]==target ) return 1;
    if(target==0) return 1;
    return 0;

}
if(dp[index][abs(target)]!=-1) return dp[index][abs(target)];

    int take = (target-nums[index]>=0)?f(index-1,target-nums[index],nums,dp):0;
    int ntake = f(index-1,target,nums,dp);
    return dp[index][abs(target)]= take + ntake;

    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int s=0;
        for(auto x:nums) s+=x;
        if((target+s)%2!=0) return 0;
        vector<vector<int>> dp(nums.size(),vector<int>((abs(target)+s)/2+2,-1));
        return f(nums.size()-1,(target+s)/2,nums,dp);

    }
};