Problem
Given an array of integers, we have to print all the sub sets of the array which have sum >=k.
For example, If my array is {1,2,3,4,5}
and my k= 5, then the sets I have to print are,
{5}, {4,1}, {4,2},{4,3}.......{1,2,3,4,5}.
Solution
Permutation all possible combinations.
Do not assume all the elements are greater than 0
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Print all the sub sets of the array which have sum >=k.
Created Data : 10-08-2013
Last Modified :
============================================================================
*/
#include <list>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <algorithm>
#include <vector>
using namespace std;
void PrintSubSetGreatThanK(vector<int>& v0, int k)
{
int i(0);
while(i < v0.size()){
vector<bool> v1(v0.size(), false);
fill(v1.begin() + i, v1.end(), true);
do{
int sum(0);
for(int i = 0; i < v1.size(); ++i){
if(v1[i]) sum += v0[i];
}
if(sum >= k){
cout << "{";
for(int i = 0; i < v1.size(); ++i){
if(v1[i]){
cout << setw(4) << " " << v0[i];
}
}
cout << "} " << endl;
}
}while(next_permutation(v1.begin(), v1.end()));
i++;
}
}
void DoTest(vector<int>& v0, int k)
{
cout << "The set is " << endl;
cout << "{";
for_each(v0.begin(), v0.end(), [](int i){
cout << setw(4) << " " << i;
});
cout << "} " << endl;
cout << "The sub set which has sum >= ";
cout << k << " are as follows" << endl;
PrintSubSetGreatThanK(v0, k);
cout << "-----------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr[] = {1, 2, 3, 4, 5};
vector<int> v0(arr, arr + sizeof(arr) / sizeof(int));
DoTest(v0, 5);
int arr1[] = {-1, -2, 3, 4, 5};
vector<int> v1(arr1, arr1 + sizeof(arr1) / sizeof(int));
DoTest(v1, 5);
int arr2[] = {-6, 5};
vector<int> v2(arr2, arr2 + sizeof(arr2) / sizeof(int));
DoTest(v2, 5);
int arr3[] = {-6};
vector<int> v3(arr3, arr3 + sizeof(arr3) / sizeof(int));
DoTest(v3, 5);
return 0;
}
Output
The set is
{ 1 2 3 4 5}
The sub set which has sum >= 5 are as follows
{ 1 2 3 4 5}
{ 2 3 4 5}
{ 1 3 4 5}
{ 1 2 4 5}
{ 1 2 3 5}
{ 1 2 3 4}
{ 3 4 5}
{ 2 4 5}
{ 2 3 5}
{ 2 3 4}
{ 1 4 5}
{ 1 3 5}
{ 1 3 4}
{ 1 2 5}
{ 1 2 4}
{ 1 2 3}
{ 4 5}
{ 3 5}
{ 3 4}
{ 2 5}
{ 2 4}
{ 2 3}
{ 1 5}
{ 1 4}
{ 5}
-----------------------
The set is
{ -1 -2 3 4 5}
The sub set which has sum >= 5 are as follows
{ -1 -2 3 4 5}
{ -2 3 4 5}
{ -1 3 4 5}
{ -1 -2 4 5}
{ -1 -2 3 5}
{ 3 4 5}
{ -2 4 5}
{ -2 3 5}
{ -2 3 4}
{ -1 4 5}
{ -1 3 5}
{ -1 3 4}
{ 4 5}
{ 3 5}
{ 3 4}
{ 5}
-----------------------
The set is
{ -6 5}
The sub set which has sum >= 5 are as follows
{ 5}
-----------------------
The set is
{ -6}
The sub set which has sum >= 5 are as follows
-----------------------
Press any key to continue . . .