# Partition Problem using dynamic programming in C

The Partition Problem is to determine if, given a set of positive integers, there is a subset that sums to precisely half of the sum of the set. For example, given the numbers from 1 to 7, their sum is 28, half of which is 14, and the subset (2, 3, 4, 5} sums to 14, so this is a positive instance. The partition problem is NP-complete, but can be solved in pseudo-polynomial time using dynamic programming.

The algorithm works by constructing an array with entries for every number from 0 to the sum of the set, and filling in the cells that are the sum of some subset. Once complete, the solution can be read back from the middle cell of the array, which corresponds to a subset that sums to half of the total sum. At first, only the 0 cell is filled in, because it is always possible to find a subset that sums to 0 — the empty set. After that, the cells to fill in are found by simulating repeated additions of the numbers from the set to the already-filled-in cells. For example, if the cell for some number $$m$$ is already filled in, and the set contains the number $$n$$, then the cell $$m + n$$ can be filled in. When a cell is filled in, a pointer is set to point back to the number from which it has been derived so that the solution can be read back.

Below is the code in C. The function partition() takes an array of numbers, its length, and the address of a pointer to which to attach the solution array. It returns the number of elements in the solution subset if there is a partition, or 0 otherwise.

struct partition_entry {
unsigned int value;
unsigned int truth;
unsigned int count;
struct partition_entry *prev;
};
typedef struct partition_entry partition_entry;

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

int compare_unsigned_ints(const unsigned int *p1, const unsigned int *p2)
{
if (*p1 > *p2) {
return 1;
}
if (*p1 < *p2) {
return -1;
}
return 0;
}

unsigned int min(unsigned int first, unsigned int second)
{
if (first < second) {
return first;
}
return second;
}

unsigned int partition(unsigned int *numbers, size_t n, unsigned int **solution)
{
unsigned int total = sum(numbers, n);
int i, j, rightmost = 0, size;
partition_entry *partitions;
if (total % 2 == 1) {
/* Total is odd */
*solution = NULL;
return 0;
}
/* Initialise array */
partitions = malloc((total + 1) * sizeof(partition_entry));
if (partitions == NULL) {
*solution = NULL;
return 0;
}
for (i = 0; i <= total; i++) {
partitions[i].value = i;
partitions[i].truth = 0;
partitions[i].count = 0;
partitions[i].prev = NULL;
}
partitions[0].truth = 1;
/* Sort the numbers */
qsort(numbers, n,
sizeof(unsigned int), (int(*)(const void *, const void *))compare_unsigned_ints);
/* Fill in the sums and build chains */
for (i = 0; i < n; i++) {
for (j = rightmost; j >= 0; j--) {
if (partitions[j].truth && !partitions[j + numbers[i]].truth) {
partitions[j + numbers[i]].truth = 1;
partitions[j + numbers[i]].count = partitions[j].count + 1;
partitions[j + numbers[i]].prev = &partitions[j];
}
}
rightmost = min(total / 2, rightmost + numbers[i]);
}
if (partitions[total / 2].truth) {
/* Success, read back the solution */
partition_entry *ptr = &partitions[total / 2];
unsigned int number = ptr->value;
size = partitions[total / 2].count;
*solution = malloc(size * sizeof(unsigned int));
if (*solution) {
for (i = 0, j = size - 1; i < size; i++, j--) {
ptr = ptr->prev;
(*solution)[j] = number - ptr->value;
number = ptr->value;
}
}
else {
size = 0;
}
}
free(partitions);
return size;
}


Here is an example that looks for a partition of the numbers from 1 to 7:

int main(void)
{
unsigned int numbers[] = {7, 6, 5, 4, 3, 2, 1};
const size_t len = sizeof(numbers) / sizeof(numbers[0]);
unsigned int *solution;
unsigned int i;
unsigned int size = partition(numbers, len, &solution);
printf("Partition size: %d\n", size);
for (i = 0; i < size; i++) {
printf("%u ", solution[i]);
}
putchar('\n');
free(solution);
return 0;
}


The output:

Partition size: 4
2 3 4 5