Partition Equal Subset Sum Geeks For Geeks and LeetCode
class Solution{
static int equalPartition(int n, int arr[])
{
int sum=0;
for(int i=0;i<n;i++){
sum=sum+arr[i];
}
if(sum%2!=0){
return 0;
}
else{
int t[][]=new int[n+1][sum+1];
sum=sum/2;
for(int i=0;i<n+1;i++){
for(int j=0;j<sum+1;j++){
if(i==0){
t[i][j]=0;
}
if(j==0){
t[i][j]=1;
}
}
}
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]=Integer.max((t[i-1][j-arr[i-1]]),(t[i-1][j]));
}
}
}
return t[n][sum];
}
}
}
Approach:
First, we will add up all the elements of the array and find out the sum. If the sum is even then only we can do partition else we can't.
Then we will find out half of the sum and now we need to find a subset with that sum. If exist then return 1 else return 0. (similar to subset sum problem)
Now we will initialize 2d array with conditions with 0 for i==0 and with 1 for j==0. It is so because
1. finite elements with 0 sum is possible
2. finite sum with 0 elements is not possible
We will now start traversing the array further from index 1 and see if the element has a value more than the sum then rejects it and traverse further. If the element has a value less than the sum then we have a choice of either including it or not.
TIME:O(N*SUM)[Geeks for Geeks time: 0.2/1.2][LeetCode Time: 89ms faster than 14.15%]
SPACE:O(N*SUM) [LeetCode Memory: 51.3MB less than 17.27%]
Thanks for Reading.😇
***************************************************************************
Geeks for Geeks Equal Sum Partition
Memoize Approach:
class Solution{
static int equalPartition(int n, int arr[]){
int sum=0;
for(int i=0;i<n;i++){
sum=sum+arr[i];
}
if(sum%2==0){
int a=knapsackSolve(n,arr,sum/2);
return a;
}
else{
return 0;
}
}
static int knapsackSolve(int n, int[] arr, int sum){
int t[][]=new int[n+1][sum+1];
for(int i=0;i<n+1;i++){
for(int j=0;j<sum+1;j++){
t[i][j]=-1;
}
}
if(n==0 && sum==0){
return 1;
}
if(n==0 && sum!=0){
return 0;
}
if(sum==0){
return 1;
}
if(t[n][sum]!=-1){
return t[n][sum];
}
else{
if(arr[n-1]>sum){
t[n][sum]=knapsackSolve(n-1,arr,sum);
}
else{
t[n][sum]=Integer.max(knapsackSolve(n-1,arr,sum),knapsackSolve(n-1,arr,sum-arr[n-1]));
}
return t[n][sum];
}
}
}
Comments
Post a Comment