# Subset-Sum with backtracking in C

The subset-sum problem is to find a subset of a set of integers that sums to a given value. The decision problem of finding out if such a subset exists is NP-complete. One way of solving the problem is to use backtracking. This is a backtracking solution in C that finds all of the subsets that sum to the target value.

typedef void(*subset_sumfn)(const unsigned int *, size_t);

static unsigned int promising(int i, size_t len, unsigned int weight, unsigned int total,
unsigned int target, const unsigned int *weights)
{
return (weight + total >= target) && (weight == target || weight + weights[i + 1] <= target);
}

static unsigned int sum(const unsigned int *weights, size_t len)
{
unsigned int total = 0;
unsigned int i;
for (i = 0; i < len; i++) {
total += weights[i];
}
}

static void subset_sum_recursive(const unsigned int *weights, size_t len, unsigned int target,
int i, unsigned int weight, unsigned int total, unsigned int *include, subset_sumfn fun)
{
if (promising(i, len, weight, total, target, weights)) {
if (weight == target) {
fun(include, i + 1);
}
else if (i < (int)len - 1){
include[i + 1] = 1;
subset_sum_recursive(weights, len, target, i + 1, weight + weights[i + 1],
total - weights[i + 1], include, fun);
include[i + 1] = 0;
subset_sum_recursive(weights, len, target, i + 1, weight,
total - weights[i + 1], include, fun);
}
}
}

void subset_sum(const unsigned int *weights, size_t len, unsigned int target, subset_sumfn fun)
{
const unsigned int total = sum(weights, len);
unsigned int *include = calloc(len, sizeof(unsigned int));
if (include == NULL) {
return;
}
subset_sum_recursive(weights, len, target, -1, 0, total, include, fun);
free(include);
}

int main(void)
{
unsigned int weights[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
const unsigned int len = sizeof(weights) / sizeof(unsigned int);
const unsigned int target = 7;
subset_sum(weights, len, target, print_vector);
return 0;
}


The output is in the form of binary strings showing which elements of the original set are in the subset, so for example the first binary string corresponds to 1 + 2 + 4 = 7.

1 1 0 1
1 0 0 0 0 1
0 1 0 0 1
0 0 1 1
0 0 0 0 0 0 1