Subset Sum Problem Geeks For Geeks
class Solution{
static boolean isSubsetSum(int n, int arr[], int sum){
boolean [][] t=new boolean[n+1][sum+1];
for(int i=0;i<n+1;i++){
for(int j=0;j<sum+1;j++){
if(i==0){
t[i][j]=false;
}
if(j==0){
t[i][j]=true;
}
}
}
for(int i=1;i<n+1;i++){
for(int j=1;j<sum+1;j++){
if(arr[i-1]>j){
t[i][j]=t[i-1][j];
}
else{
t[i][j]=(t[i-1][j-arr[i-1]]) || (t[i-1][j]);
}
}
}
return t[n][sum];
}
}
APPROACH: Dynamic Programming
Here we will first initialize boolean matrix t of size n+1 and sum+1 with true or false.
If the sum is 0 then the size of the array does not matter and hence true will be stored.
If the sum is non zero but the size of an array is non zero then it is not possible. Hence false will be stored.
If an element has more value than the required sum then it will be neglected.
If the element has less value or equal value then the required sum it will be taken under consideration.
Now it depends further either to take that element or not which will be decided by or operation between yes or no.
In such a manner we will traverse the whole t array filling values in each cell and return the last cell result.
TIME: O(N*SUM) [Geeks For Geeks Time: 0.2/1.2]
SPACE: O(N*SUM)
Thanks for Reading.😇
Recursive Solution ***************************************************************
class Solution{
static boolean isSubsetSum(int n, int arr[], 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;
}
else{
if(arr[n-1]>sum){
return isSubsetSum(n-1,arr,sum);
}
else{
return isSubsetSum(n-1,arr,sum) || isSubsetSum(n-1,arr,sum-arr[n-1]) ;
}
}
}
}
Comments
Post a Comment