class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int n=nums.size();
        if(n==0) return 0;
        map<int, int>cur;
        cur[nums[0]]=1;
        cur[-nums[0]]+=1;  
        map<int, int>nxt;
        for(int i=1; i<n; i++)
        {    
            nxt.clear();
            for(auto it=cur.begin(); it!=cur.end(); it++)
            {
                nxt[it->first+nums[i]]+=cur[it->first];
                nxt[it->first-nums[i]]+=cur[it->first];
            }   
            cur=nxt; 
        }
        if(n==1 &&(nums[0]==S || -nums[0]==S))
            return 1;
        return nxt[S]; 
      }
};