Subset Sum Using Memoization

 import java.util.Scanner;

class KnapsackSolve{

public boolean knapsack(int[] arr, int n, int sum){

//Base Condition

if(n==0){

return false;

}

else if(sum==0 && n!=0){

return true;

}

else if(sum==0 && n==0){

return true;

}

boolean t[][]=new boolean[n+1][sum+1];

for(int i=1;i<n+1;i++){

for(int j=1;j<sum+1;j++){

t[i][j]=false;

}

}

if(t[n][sum]!=false){

return t[n][sum];

}

else{

if(arr[n-1]>sum){

t[n][sum]=knapsack(arr,n-1,sum);

}

else{

t[n][sum]=knapsack(arr,n-1,sum) || knapsack(arr,n-1,sum-arr[n-1]);

}

return t[n][sum];

}

}

}

class SubsetSumMemoize{

public static void main(String arg[]){

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

int arr[]=new int[n];

for(int i=0;i<n;i++){

arr[i]=sc.nextInt();

}

int sum=sc.nextInt();

KnapsackSolve obj1=new KnapsackSolve();

boolean c=obj1.knapsack(arr,n,sum);

System.out.println(c);

}

}

TIME:O(N*SUM)

SPACE:O(N*SUM)