-
Notifications
You must be signed in to change notification settings - Fork 3
/
sub set sum.cpp
40 lines (40 loc) · 1.19 KB
/
sub set sum.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <numeric>
using namespace std;
#define MAX_ELEMENT 15+1
int wt[MAX_ELEMENT];
bool include[MAX_ELEMENT];
int n,W,weight,total;
bool promising (int i, int weight, int total){
return ((weight + total >= W) &&(weight == W || weight + wt[i+1] <= W));
}
//i = index of current item. i.e depth of tree
//weight = summed weight of items included so far.
//total = total weight of notyetconsidered items.
void sum_of_subsets (int i, int weight, int total){
if (promising(i, weight, total)) {
if (weight == W) {
for(int k = 1;k<=i;k++)if(include[k])printf("%d%c", wt[k],k==i?'\n':' ');
} else {
include[i+1] = true;
sum_of_subsets(i+1, weight + wt[i+1], total- wt[i+1]);
include[i+1] = false;
sum_of_subsets(i+1, weight, total-wt[i+1]);
}
}
}
int main()
{
freopen("input.txt", "r", stdin);
while(scanf("%d", &n)==1&& n!=0){
for(int i=1;i<=n;i++)scanf("%d", &wt[i]);
scanf("%d", &W);
sort(&wt[1],&wt[1]+n);
total = accumulate(&wt[1],&wt[1]+n,0);
weight = 0;
sum_of_subsets(0,weight,total);
}
return 0;
}