Print equal sum sets of array ( Partition problem ) | Set 1 | CPP program to print equal sum two subsets of an array if it can be partitioned into subsets . ; / Function to print the equal sum sets of the array . ; / Print set 1. ; / Print set 2. ; / Utility function to find the sets of the array which / have equal sum . ; / If entire array is traversed , compare both the sums . ; / If sums are equal print both sets and return / true to show sets are found . ; / If sums are not equal then return sets are not / found . ; / Add current element to set 1. ; / Recursive call after adding current element to / set 1. ; / If this inclusion results in equal sum sets / partition then return true to show desired sets are / found . ; / If not then backtrack by removing current element / from set1 and include it in set 2. ; / Recursive call after including current element to / set 2. ; / Return true if array arr can be partitioned / into two equal sum sets or not . ; / Calculate sum of elements in array . ; / If sum is odd then array cannot be / partitioned . ; / Declare vectors to store both the sets . ; / Find both the sets . ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printSets ( vector < int > set1 , vector < int > set2 ) { int i ; for ( i = 0 ; i < set1 . size ( ) ; i ++ ) { cout << set1 [ i ] << " ▁ " ; } cout << " STRNEWLINE " ; for ( i = 0 ; i < set2 . size ( ) ; i ++ ) { cout << set2 [ i ] << " ▁ " ; } } bool findSets ( int arr [ ] , int n , vector < int > & set1 , vector < int > & set2 , int sum1 , int sum2 , int pos ) { if ( pos == n ) { if ( sum1 == sum2 ) { printSets ( set1 , set2 ) ; return true ; } else return false ; } set1 . push_back ( arr [ pos ] ) ; bool res = findSets ( arr , n , set1 , set2 , sum1 + arr [ pos ] , sum2 , pos + 1 ) ; if ( res ) return res ; set1 . pop_back ( ) ; set2 . push_back ( arr [ pos ] ) ; res = findSets ( arr , n , set1 , set2 , sum1 , sum2 + arr [ pos ] , pos + 1 ) ; if ( res == false ) if ( ! set2 . empty ( ) ) set2 . pop_back ( ) ; return res ; } bool isPartitionPoss ( int arr [ ] , int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; if ( sum % 2 != 0 ) return false ; vector < int > set1 , set2 ; return findSets ( arr , n , set1 , set2 , 0 , 0 , 0 ) ; } int main ( ) { int arr [ ] = { 5 , 5 , 1 , 11 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; if ( ! isPartitionPoss ( arr , n ) ) { cout << " - 1" ; } return 0 ; }