Subset sum problem: Difference between revisions

Content added Content deleted
(→‎{{header|C}}: shorten the example, to show all the zero sum subsets, you can kill the process if you got all you need from it. and its easier to follow without the bit math which doesn't change the time complexity anyway.)
(→‎{{header|C}}: Call it a set not path)
Line 207: Line 207:


int n = sizeof (items) / sizeof (item_t);
int n = sizeof (items) / sizeof (item_t);
int *path;
int *set;


void subsum (int i, int weight) {
void subsum (int i, int weight) {
Line 213: Line 213:
if (i && !weight) {
if (i && !weight) {
for (j = 0; j < i; j++) {
for (j = 0; j < i; j++) {
item_t item = items[path[j]];
item_t item = items[set[j]];
printf("%s%s", j ? " " : "", items[path[j]].word);
printf("%s%s", j ? " " : "", items[set[j]].word);
}
}
printf("\n");
printf("\n");
}
}
for (j = i ? path[i - 1] + 1: 0; j < n; j++) {
for (j = i ? set[i - 1] + 1: 0; j < n; j++) {
path[i] = j;
set[i] = j;
subsum(i + 1, weight + items[j].weight);
subsum(i + 1, weight + items[j].weight);
}
}
Line 225: Line 225:


int main () {
int main () {
path = malloc(n * sizeof (int));
set = malloc(n * sizeof (int));
subsum(0, 0);
subsum(0, 0);
return 0;
return 0;
Retrieved from "https://rosettacode.org/wiki/Subset_sum_problem"