Having a set of positive numbers from 0 to 9 find recursively all subsets which sums up to 10.
Algorithm 1
Take a subset. If sums up to 10 then print it. Is sums less than 10 then break. Then apply the same algorithm for any subset received by removing from the first subset one element.
Start with the initial set.
C++ code :
#include <iostream>
#include <vector>
const int SET_SIZE = 10;
typedef std::vector<bool> settype;
const int SUM=10;
void print(const settype &set) {
for (int i=0; i<SET_SIZE; i++) {
if (set[i]) std::cout<<i+1<<' ';
}
std::cout<<std::endl;
}
void run_set(settype set,int sum, int remove) {
if (remove != -1) {
set[remove] = false;
sum -= (remove + 1);
}
if (sum < SUM) return;
if (sum == SUM) print(set);
for (int i = remove+1; i<SET_SIZE; i++) {
if (set[i]) {
run_set(set,sum,i);
}
}
}
int main(int argc, char **argv) {
bool init_set[SET_SIZE] = { true,false,true,true,false,true,true,true,false,true};
settype setOfNum(init_set,init_set + sizeof(init_set) / sizeof(bool));
int sum = 39;
run_set(setOfNum,sum,-1);
return 0;
}
Algorithm 2
Apply a variant of 0-1 snapsack problem.
Take a subset.
- If subset sums to less than 10 then break.
- Remove last element and find all subsets which sums to 10.
- Remove last element and find all subsets which sums to 10 minus the last element.
- Sums set of sets received in point 1) and set of sets received in point 2) plus the last (removed) element.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int SUM=10;
typedef std::vector<int> settype;
typedef std::vector<settype> listofset;
void print(const settype &set) {
for (int k=0; k<set.size(); k++) {
cout << set[k] << ' ';
}
cout << endl;
}
void D(int i,int w,const settype &set,listofset &outlist) {
listofset list1,list2;
i--;
if ((w == 0) || (i == -1)) {
outlist = list1;
return;
}
D(i,w,set,list1);
D(i,w-set[i],set,list2);
outlist = list1;
for (int k=0; k<list2.size(); k++) {
list2[k].push_back(set[i]);
outlist.push_back(list2[k]);
}
if (set[i] == w) {
settype t;
t.push_back(set[i]);
outlist.push_back(t);
return;
}
}
int main(int argc, char **argv) {
int init_set[] = { 1,9,10,2,7 };
settype set(init_set,init_set + sizeof(init_set) / sizeof(int));
listofset outset;
D(set.size(),SUM,set,outset);
for (int i=0; i<outset.size(); i++) {
cout << i << ":";
print(outset[i]);
}
return 0;
}
Remarks
Of course - it is an artificial problem, the best way is to apply simple iteration without recursion.
Another problem is the complexity. The number of all subsets of n-element set is exponential (2 to power n). So the algorithm is no worse than that. But is it possible to do it faster - in polynomial complexity.
