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