class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        /* basically the question is similiar to divide into 2 subsets such that there 
        difference is equal to target
        */

        int t = 0 ,n = nums.length;
        for(int a : nums)
        t+=a;
        
        int sum = (t-target)/2;
        if(sum < 0 || (t-target)%2 != 0) return 0;

        return solve(nums , n-1 , sum , new Integer[n][sum+1] );
    }

    //R-> 2^n M-> n*sum | sc- n + n*sum
	public int solve(int nums[] , int i , int sum , Integer[][] dp){
        if(i == 0){
            if(sum == 0 && nums[0] == 0) return 2;  //take = notake , as its 0
            
            //if sum = 0 dont take , if sum = nums[0] take it
            else if(sum == 0 || sum == nums[0]) return 1;    
            
            else
            return 0;
        }
        if(dp[i][sum] != null)
        return dp[i][sum];
        
        int notake = solve(nums , i-1 , sum , dp);
        
        int take = 0;
        if(sum - nums[i] >= 0)
        take = solve(nums , i-1 , sum-nums[i] , dp);
        
        return dp[i][sum]=take+notake;
        
    }
}