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#
Comments
Post a Comment