Post date: Jul 29, 2013 12:11:10 PM
Problem
Given a set of n integers and sum of all numbers is at most K.
find the subset of these n elements whose sum is exactly half of the total sum
of n numbers;Given a set of n integers and sum of all numbers is at most K.
find the subset of these n elements whose sum is exactly half of the total sum of n numbers;
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the subset whose sum is exactly half of the total sum
Created Data : 29-07-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <numeric>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
void FindSubSet(int* arr, int len, int sum, vector<int>& subSet, int index, bool& found)
{
if(sum == 0){
found = true;
cout << "The subset is ";
copy(subSet.begin(), subSet.end(), ostream_iterator<int>(cout, " " ));
cout << endl;
return;
}
for(int i = index; i < len; ++i){
if(arr[i] <= sum){
subSet.push_back(arr[i]);
FindSubSet(arr, len, sum - arr[i], subSet, i + 1, found);
subSet.pop_back();
}
}
}
bool FindHalfSum(int* arr, int len)
{
int sum = accumulate(arr, arr + len, 0);
if(sum & 1 == 1) return false;
sum >>= 1;
vector<int> subSet;
bool found(false);
for(int i = 0; i < len; ++i){
if(arr[i] <= sum){
subSet.push_back(arr[i]);
FindSubSet(arr, len, sum - arr[i], subSet, i + 1, found);
subSet.pop_back();
}
}
return found;
}
void DoTest(int* arr, int len)
{
cout << "The array is " << endl;
copy(arr, arr + len, ostream_iterator<int>(cout, " "));
cout << endl;
if(!FindHalfSum(arr, len)){
cout << "No subset meets the requirement" << endl;
}
cout << "---------------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr[] = {1, 2, 3, 4, 5, 6};
DoTest(arr, sizeof(arr) / sizeof(int));
int arr1[] = {7, 2, 3, 4, 5, 6, 9};
DoTest(arr1, sizeof(arr1) / sizeof(int));
int arr2[] = {-7, -2, 3, 4, 5, 6, 9};
DoTest(arr2, sizeof(arr2) / sizeof(int));
int arr3[] = {2};
DoTest(arr3, sizeof(arr3) / sizeof(int));
int arr4[] = {-7, -2};
DoTest(arr4, sizeof(arr4) / sizeof(int));
int arr5[] = {-2, -2};
DoTest(arr5, sizeof(arr5) / sizeof(int));
return 0;
}
Output
The array is
1 2 3 4 5 6
No subset meets the requirement
---------------------------
The array is
7 2 3 4 5 6 9
The subset is 7 2 3 6
The subset is 7 2 4 5
The subset is 7 2 9
The subset is 7 5 6
The subset is 2 3 4 9
The subset is 3 4 5 6
The subset is 3 6 9
The subset is 4 5 9
---------------------------
The array is
-7 -2 3 4 5 6 9
The subset is -7 -2 3 4 5 6
The subset is -7 -2 3 6 9
The subset is -7 -2 4 5 9
The subset is -7 3 4 9
The subset is -2 5 6
The subset is 3 6
The subset is 4 5
The subset is 9
---------------------------
The array is
2
No subset meets the requirement
---------------------------
The array is
-7 -2
No subset meets the requirement
---------------------------
The array is
-2 -2
The subset is -2
The subset is -2
---------------------------
Press any key to continue . . .