Hi folks, Welcome back once again.

In this article, we will check if an array can be partitioned into two parts so that the sum of elements in both sets/parts is the same.

prerequisite : Knapsack approach and subset sum approach

In the above example, we have partitioned two subsets having an equal sum, The first part contains {1, 5, 5} (5+5+1 = 11) having a sum of 11, and the second part has only one element whose sum is {11}. In this case, we have successfully divided the array into two equal parts.

Approach

We can find the approach by just applying basic mathematics.

1. we can only divide the array into two subset whose sum is even. (we are not considering fractional division)

2. let's understand this from the above example {1,5,5,11} the sum of this array is 22 which is even so we can divide this array into two equal subset having 11-11 sum.

And {2,5,5,11} this array has sum 23 and 23 can not be divided into two equal non fractional subset.

Hence the arrays having odd sum value can not have two subset having equal sum.

for the even sum array just check all possible subset whose sum is equal to sum/2 because if we consider even sum arrays can be divided into s1 and s2 and if these two subset have equal sum then we can define s1 = s2

Here find the possible subset whose sum is equal to k where k is (sum of original array / 2).

Algorithm

1) Calculate sum of the array. If sum is odd, there can not be two subsets with equal sum, so return false.

2) If sum of array elements is even, calculate sum/2 and find a subset of array with sum equal to sum/2.

The first step is simple. The second step is crucial, it can be solved either using recursion or Dynamic Programming.

Recursive Approach

Implementation

int solve(int N, int arr[],int sum, vector<vector<int> > &dp){

        if(N==0){
            return 0;
        }
        if(dp[N][sum]!=-1){
            return dp[N][sum];
        }

        if(sum==arr[N-1]){
            return 1;
        }

        if(arr[N-1] <= sum){
            return dp[N][sum] = solve(N-1,arr,sum-arr[N-1],dp) || solve(N-1,arr,sum,dp);
        }
        else{
            return dp[N][sum] = solve(N-1,arr,sum,dp);
        }


    }

    int equalPartition(int N, int arr[])
    {
        int sum=0;       
        for(int i=0;i<N;i++){
            sum+=arr[i];
        }
        vector<vector<int> > dp( N+1 , vector<int> (sum+1, -1));

        if(sum%2==0){ // if sum is even then find all subset having sum  = sum of array /2
           int d = solve(N,arr,sum/2,dp);  
           return d;
        }

        return 0; // if sum is odd then return false/0


    }

Conclusion

• Time Complexity: O(sum*n)
• Space Complexity: O(sum*n)

Stay tuned with us on this journey of Competitive Programming.

I hope you liked it!. Let's catch up in the next articles.

Practice Link: Click Here

If you liked it, Please Support Me