Q14 Subset Sum Equal To K - Coding Ninjas

import java.util.* ;
import java.io.*; 
public class Solution {
    public static boolean subsetSumToK(int n, int k, int arr[]){
        // return solve(arr , n-1 , k , new Boolean[n][k+1]);

        //Tabulization -> n*k  | Sc- n*k
        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;
                }
            }
        }

        return dp[n-1][k];
    }

    //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;
    }
}