Subset-Sum Problem with Backtracking in C

The subset-sum problem is a classic computational challenge in computer science. The task is to find a subset of a set of integers that sums up to a specified value. Even though determining if such a subset exists is classified as an NP-complete problem, there are various algorithms to approach it, including backtracking.

This article presents a solution for the subset-sum problem using backtracking in the C programming language. Specifically, it will find all possible subsets from a set of integers that sum up 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;
}

Sample Output:

The result is represented as binary strings that indicate which elements from the initial set belong to the subset. For instance, the initial binary string corresponds to 1 + 2 + 4, resulting in a sum of 7.

The example provided in the code yields the following results:

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

Conclusion

The subset-sum problem, though computationally complex, can be tackled using algorithms like backtracking. The provided C code offers a comprehensive approach to finding all subsets that meet a given target sum. On a related note, for those interested in web automation, another article dives into how to execute JavaScript in Python using Selenium.