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]; } return total; } 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