Subset Sum using Recursive Approach
import java.util.Scanner;
class KnapsackSolve{
public boolean knapsack(int[] arr, int n, int W){
//Base Condition
if(n==0 && w!=0){
return false;
}
else if(W==0){
return true;
}
else{
if(arr[n-1]>W){
return knapsack(arr,n-1,W);
}
else{
return knapsack(arr,n-1,W) || knapsack(arr,n-1,W-arr[n-1]) ;
}
}
}
}
class SubsetSumRecursive{
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 W=sc.nextInt();
KnapsackSolve obj1=new KnapsackSolve();
boolean c=obj1.knapsack(arr,n,W);
System.out.println(c);
}
}
Comments
Post a Comment