Q18 Partitions with Given Difference | Practice | GeeksforGeeks

class Solution{
    int m = (int)1e9+7;
    public int countPartitions(int n, int d, int nums[]){
        
        //s1-s2 = d -> s1 = total-s1 -> s2 = (totalsum-d/2)
        //find count of subsets which is equal to (d-totalsum/2)
        //(d-totalsum)/2 should be > 0 && should be even
        int t = 0;
        for(int a : nums)
        t+=a;
        
        int sum = (t-d)/2;
        if(sum < 0 || (t-d)%2 != 0) return 0;
        
        int[][] dp = new int[n][sum+1];
	   //base case
	    if(nums[0] == 0)
        dp[0][0] = 2;
        else
        dp[0][0] = 1;
        if(nums[0] != 0 && nums[0] <= sum)
        dp[0][nums[0]] = 1;
        
	   //rest of the recursion logic
	   for(int i = 1 ;i < n ; i++){
	       for(int j = 0 ; j < sum+1 ; j++){
                
                int notake = dp[i-1][j];
                int take = 0;
                if(j - nums[i] >= 0)
                take = dp[i-1][j-nums[i]];
                
                dp[i][j]=(take+notake)%m;
	       }
	   }
	   
	   return dp[n-1][sum];
    }
    
    	//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)%m;
        
    }
}