/**
knakul853
**/
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {

        int n = nums.size();
        int sm = accumulate(nums.begin(), nums.end(), 0);

        if(sm < S || ((sm + S) &1))return 0;
        return f(nums, (sm + S)/2);


    }

    int f(vector<int>& nums, int s)
    {
        vector<int>dp(s+1,0);
        dp[0] = 1;

        for(auto num:nums)
        {
            for(int j=s;j>=num;j--)
            {
                dp[j]+=dp[j-num];
            }
        }
        return dp[s];
    }


};

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {

        int n = nums.size();
        return f(nums, n, 0, 0, S);

    }

    int f(vector<int>& nums, int n, int sm,int id, int s)
    {
        if(id == n && s == sm)
        {
            return 1;
        }
        if(id==n)return 0;

        return f(nums, n, sm+nums[id], id+1, s) + f(nums,n, sm - nums[id], id+1, s);
    }
};