Question

C++ program which partitions n positive integers into two disjoint sets with the same sum. Consider all possible subsets of the input numbers.

All in one C++ file.

This is the sample Input 1

6
3 5 20 7 1 14

Output 1

Equal Set: 1 3 7 14

This is the sample Input 2

5
10 8 6 4 2

Output 2

Equal Set: 0

Answer 1

#include <bits/stdc++.h>
using namespace std;
/// It is the Function that prints the equal sum sets of the array.
void printing(vector<int> array1, vector<int> array2)
{
int i;
cout << "Equal set:";
for (i = 0; i < array1.size(); i++) {
cout << array1[i] << " ";
}
cout << "\n";
for (i = 0; i < array2.size(); i++) {
cout << array2[i] << " ";
}
}
  
/// Utility function to find the sets of the array which
/// have equal sum.
bool findingsets(int arr[], int n, vector<int>& array1,
vector<int>& array2, int sum1, int sum2, int pos)
{
  
/// If entire array is traversed, compare both the sums.
if (pos == n) {
  
/// If both the sums are equal print them
if (sum1 == sum2) {
printing(array1, array2);
return true;
}
  
/// If sums are not equal then return false
else
return false;
}
  
/// Adding the present element to array1.
array1.push_back(arr[pos]);
  
/// Recursive call after adding current element to array1.
bool res = findingsets(arr, n, array1, array2, sum1 + arr[pos],
sum2, pos + 1);
  
/// If this inclusion results has equal sum sets partition then return true.
if (res)
return res;
  
/// If it is not equal then backtrack by removing current element from array1 and include it in array2.
array1.pop_back();
array2.push_back(arr[pos]);
  
/// recursion after including current element to array2.
res = findingsets(arr, n, array1, array2, sum1, sum2 + arr[pos],
pos + 1);
if (res == false)
if (!array2.empty())
array2.pop_back();
  
return res;
}
  
/// Return true if the array can be partitioned into two equal disjoint sets
bool checkposition(int arr[], int n)
{
/// Calculating the sum of all the elements in the array
int sum = 0;
  
for (int j = 0; j < n; j++)
sum =sum+arr[j];
  
/// we can divide the array only if the sum is even.
if (sum % 2 != 0)
return false;
  
/// Declaring two vectors to store the two disjoint sets
vector<int> array1, array2;
  
/// This function checks whether the array can be divided into sets with equal sum
return findingsets(arr, n, array1, array2, 0, 0, 0);
}
// Main Function
int main()
{
   int input;
   cout << "Enter a number: ";
   cin >> input;
int arr[input],i;
for (int i = 0; i < input; ++i)
{
cin >> arr[i];
}
int n = sizeof(arr) / sizeof(arr[0]);
if (!checkposition(arr, n)) {
cout << "Equal set:0";
}
return 0;
}