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

Popular posts from this blog

Java Date And Time HackerRank

Recursive Sequence Geeks For Geeks Problem Of The Day 12-02-2024

Minimum Indices HackerEarth