Target sum

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        /*
        it is similar to subset sum equal to target
        given (+1 + 1 + 1 + 1) - (1) = 3
        i.e. s1-s2 = k ( s1 and s2 are the subsets)
        we know  s1+s2 = sum
        i.e k+s2+s2 = sum => s2 = (sum-k)/2

        edge cases : sum-k>=0 because, 0<=nums[i]<=1000 given So,sum can't be less than 0
        also (sum-k)/2 can not be fraction, as s2 can't be equal to a fraction value as the array is integer.
        */
        int sum  =0;
        for(int i : nums){
            sum+=i;
        }
        int k = (sum-target)/2;
        if((sum-target)<0 || (sum-target)%2!=0) return 0;
        return subsetSumEqTarget(0,nums,k);
    }
    public int subsetSumEqTarget(int index, int nums[], int k){
        //base case

        if(index == nums.length-1){
            if(k ==0 && nums[index] ==k) return 2;
            if(k ==0 || nums[index]==k) return 1;
            return 0;
        }
        int take = 0;
        if(k>=nums[index]){
            take = subsetSumEqTarget(index+1,nums,k-nums[index]);
        }
        int dontTake = subsetSumEqTarget(index+1,nums,k);
        return take + dontTake;

    }
}

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        /*
        it is similar to subset sum equal to target
        given (+1 + 1 + 1 + 1) - (1) = 3
        i.e. s1-s2 = k ( s1 and s2 are the subsets)
        we know  s1+s2 = sum
        i.e k+s2+s2 = sum => s2 = (sum-k)/2

        edge cases : sum-k>=0 because, 0<=nums[i]<=1000 given So,sum can't be less than 0
        also (sum-k)/2 can not be fraction, as s2 can't be equal to a fraction value as the array is integer.
        */
        int sum  =0;
        for(int i : nums){
            sum+=i;
        }
        int k = (sum-target)/2;
        if((sum-target)<0 || (sum-target)%2!=0) return 0;
        int dp[][] = new int[nums.length][k+1];
        for(int d[] : dp) Arrays.fill(d,-1);
        return subsetSumEqTarget(0,nums,k,dp);
    }
    public int subsetSumEqTarget(int index, int nums[], int k,int dp[][]){
        //base case

        if(index == nums.length-1){
            if(k ==0 && nums[index] ==k) return 2;
            if(k ==0 || nums[index]==k) return 1;
            return 0;
        }
        if(dp[index][k]!=-1) return dp[index][k];
        int take = 0;
        if(k>=nums[index]){
            take = subsetSumEqTarget(index+1,nums,k-nums[index],dp);
        }
        int dontTake = subsetSumEqTarget(index+1,nums,k,dp);
        return dp[index][k] = take + dontTake;

    }
}