Q16 Minimum sum partition | Practice | GeeksforGeeks

class Solution
{

	public int minDifference(int arr[], int n) 
	{   
	   // int n = arr.length;
	    int k = 0;
	    for(int t : arr)
	    k += t;
	    
	    //find all subset sums equal to total of k ,then traverse the last row 
	    //if it is true fin min difference by (totsum - dp[n-1][j]);
	    boolean[][] dp = new boolean[n][k+1];
        for(int i = 0 ;i < n ; i++){
            for(int j = 0 ; j < k+1 ; j++){
                if(i == 0){
                    if(j == 0 || j-arr[0] == 0)
                    dp[i][j] = true;

                    else dp[i][j] = false;
                }
                else{
                    boolean take = false , notake = false;

                    if(j-arr[i] >= 0)
                    take = dp[i-1][j-arr[i]];

                    notake = dp[i-1][j];

                    dp[i][j] = take||notake;
                }
            }
        }
        
        int ans= (int)1e9;
		for(int j = 0 ;j < k+1 ; j++){
			if(dp[n-1][j])
			ans = Math.min(ans , Math.abs((k-j) - j ));
		}
		return ans;
	} 
	
	//Recursion -> 2^(n*k) Memoization-> 2*n*k | SC- n*k + n*k
    public static boolean solve(int arr[] ,int idx ,  int k , Boolean[][] dp){
        if(k < 0)
        return false;

        if(idx == 0){
            if(k == 0 || k - arr[0]== 0)
            return true;

            return false;
        }
        if(dp[idx][k] != null)
        return dp[idx][k];

        //take / notake faith calls from (n-1,k) 
        boolean take = solve(arr ,idx-1 , k-arr[idx] , dp );
        boolean notake = solve(arr , idx-1 , k , dp);
        
        return dp[idx][k] = take||notake;
    }
	
}