Q17 Perfect Sum Problem | Practice | GeeksforGeeks

class Solution{
    int m = (int) 1e9 + 7;
	public int perfectSum(int nums[],int n, int sum) 
	{   
	
	   // return solve(nums , n-1 , sum , new Integer[n][sum+1]);
	   
	   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;
        
    }
}