Tag Archives: Subset-Sum

Subset-Sum using dynamic programming in C

The Subset-Sum problem is to determine, given a set of integers, whether there is a subset that sums to a given value. The problem is NP-complete, but can be solved in pseudo-polynomial time using dynamic programming.

Below is an implementation in C. The algorithm works by filling in a table. The rows of the table correspond to values from 0 to the target value, while the columns correspond to elements of the set. Each cell in the table repesents a solution for that row’s total using the elements chosen from the columns to the left. When the table has been filled, the truth value in the bottom-right-hand cell will indicate whether there is a successful solution. I have used chains of pointers within the table to allow the elements in the solution to be read back.

struct entry {
    unsigned int truth;
    int element;
    unsigned int count;
    struct entry *prev;
};
typedef struct entry entry;
 
unsigned int subset_sum(const unsigned int *weights, size_t len, unsigned int target,
        unsigned int **solution)
{
    entry **table;
    unsigned int i, j;
    entry *head;
    unsigned int count = 0;

    table = malloc((target + 1) * sizeof(entry *));
    for (i = 0; i <= target; i++) {
        table[i] = malloc((len + 1 ) * sizeof(entry));
    }
 
    for (i = 0; i <= target; i++) {
        for (j = 0; j <= len; j++) {
            /* First row */
            if (i == 0) {
                table[i][j].truth = 1;
                table[i][j].element = -1;
                table[i][j].count = 0;
                table[i][j].prev = NULL;
            }
            else if (j == 0) {
                /* First column */
                table[i][j].truth = 0;
                table[i][j].element = -1;
                table[i][j].count = 0;
                table[i][j].prev = NULL;
            }
            else {
                /* Initialise for don't add element case */
                table[i][j].truth = table[i][j-1].truth;
                table[i][j].prev = &table[i][j - 1];
                table[i][j].element = -1;
                table[i][j].count = table[i][j - 1].count;
                if (i >= weights[j-1]) {
                    /* Can add element */
                    if (!table[i][j].truth) {
                        /* Add element */
                        table[i][j].truth = table[i - weights[j-1]][j-1].truth;
                        table[i][j].element = j - 1;
                        table[i][j].count = table[i - weights[j-1]][j-1].count + 1;
                        table[i][j].prev = &table[i - weights[j-1]][j-1];
                    }
                }
            }
        }
    }
 
    if (!table[target][len].truth) {
        /* No solution */
        *solution = NULL;
    }
    else {
        /* Solution */
        *solution = calloc(len, sizeof(unsigned int));
    }
    if (*solution) {
        /* Read back elements */
        count = table[target][len].count;
        for (head = &table[target][len]; head != NULL; head = head->prev) {
            if (head->element != -1) {
                (*solution)[head->element]++;
            }
        }
    }
 
    for (i = 0; i <= target; i++) {
        free(table[i]);
    }
    free(table);

    return count;
}

Here is an example program:

int main(void)
{
    unsigned int weights[] = {5, 7, 1, 3, 11, 9};
    unsigned int target = 14;
    const size_t len = sizeof(weights) / sizeof(weights[0]);
    unsigned int *solution;
    const unsigned int count = subset_sum(weights, len, target, &solution);
    if (count) {
        unsigned int i;
        printf("Found a solution\n");
        printf("Elements:\n");
        for (i = 0; i < len; i++) {
            if (solution[i]) {
                printf("%u ", weights[i]);
            }
        }
        putchar('\n');
    }
    else {
        printf("No solution\n");
    }
    free(solution);

    return 0;
}

The output:

Found a solution
Elements:
3 11

Value-Independent Knapsack Problem using backtracking in C

In another post I described a backtracking algorithm for the Subset-Sum Problem, in which the aim is to find a subset of a set of weights that sums to a given weight. A related problem, which is sometimes called Subset-Sum but is also called Value-Independent Knapsack, is to find a subset of the set of weights that is the maximum weight less than or equal to the given weight, rather than the exact weight.

This problem can be thought of as a 0-1 knapsack problem in which the weights are equal to the values for all items. Like 0-1 knapsack, the problem is NP-hard, but a backtracking algorithm can produce an exact solution quite efficiently. This is a backtracking algorithm for Value Independent Knapsack in C. The function subset_sum() takes an array of weights and its size, a capacity, and an out parameter for the solution array, and returns the weight of the best set found.

static void subset_sum_recursive(const unsigned int *weights, size_t n, unsigned int capacity, 
        unsigned int *current_set, unsigned int *current_weight, unsigned int *max_set, 
        unsigned int *max_weight, unsigned int *remaining_weight, unsigned int level)
{
    if (level == n) {
        /* Found a new best set */
        *max_weight = *current_weight;
        memcpy(max_set, current_set, n * sizeof(unsigned int));
        return;
    }
    *remaining_weight -= weights[level];
    if (*current_weight + weights[level] <= capacity) {
        /* Try solutions that include this item */
        *current_weight += weights[level];
        current_set[level] = 1;
        subset_sum_recursive(weights, n, capacity, current_set, current_weight, 
                max_set, max_weight, remaining_weight, level + 1);
        *current_weight -= weights[level];
        current_set[level] = 0;
    }
    if (*current_weight + *remaining_weight > *max_weight) { 
        /* Still promising */
        subset_sum_recursive(weights, n, capacity, current_set, current_weight, 
                max_set, max_weight, remaining_weight, level + 1);
    }
    *remaining_weight += weights[level];
}

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

static unsigned int subset_sum(const unsigned int *weights, size_t n, unsigned int capacity,
        unsigned int **max_set)
{
    unsigned int current_weight = 0;
    unsigned int max_weight = 0;
    unsigned int remaining_weight = sum(weights, n);
    unsigned int *current_set = calloc(n, sizeof(unsigned int));
    *max_set = malloc(n * sizeof(unsigned int));
    if (current_set == NULL || *max_set == NULL) {
        free(current_set);
        free(*max_set);
        return 0;
    }
    subset_sum_recursive(weights, n, capacity, current_set, &current_weight, *max_set,
           &max_weight, &remaining_weight, 0);
    free(current_set);
    return max_weight;
}

Here is an example program. It prints the maximum weight found and the elements of the set:

int main(void)
{
    unsigned int weights[] = {8, 6, 2, 3};
    const size_t n = sizeof(weights) / sizeof(weights[0]);
    const unsigned int capacity = 12;
    unsigned int *set;
    unsigned int weight = subset_sum(weights, n, capacity, &set);
    unsigned int i;
    printf("%u\n", weight);
    for (i = 0; i < n; i++) {
        if (set[i]) {
            printf("%u ", weights[i]);
        }
    }
    putchar('\n');
    free(set);
    return 0;
}

The output:

11
8 3

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