Partition Equal Subset Sum| recursion | dynamic programming | geeksforgeeks

 Given an array arr[] of size N, check if it can be partitioned into two parts such that the sum of elements in both parts is the same.

Example 1:

Input: N = 4
arr = {1, 5, 11, 5}
Output: YES
Explanation: 
The two parts are {1, 5, 5} and {11}.

Example 2:

Input: N = 3
arr = {1, 3, 5}
Output: NO
Explanation: This array can never be 
partitioned into two such parts.

Your Task:
You do not need to read input or print anything. Your task is to complete the function equalPartition() which takes the value N and the array as input parameters and returns 1 if the partition is possible. Otherwise, returns 0.

Answer : 

class Solution{

public:

int sum_arr(int arr[] , int n )

{

    int sum  =0;

    for(int i =0 ; i < n ; i++)

    {

        sum += arr[i];

    }

    return sum;

}   

bool equalsum(int arr[] , int N  , int sum)

{

    if(sum == 0)

     return true;

    

    if(sum != 0 && N == 0)

     return false;

     

     if(sum < arr[N-1])

       return equalsum(arr , N-1 , sum);

     

     if(sum > arr[N-1])

      return equalsum(arr , N-1 , sum - arr[N-1])|| equalsum(arr , N-1 , sum);

}

 

    int equalPartition(int N, int arr[])

    {   

        int sum = sum_arr(arr , N);

        

        if(sum %2 == 1)

         return false;

        

        if(equalsum(arr, N , sum/2))

         return true;

        return false;

        

    }

};

References : https://practice.geeksforgeeks.org/problems/subset-sum-problem2014/1#