Answer to Question #270711 in C++ for osama

Question

Write a function that will take divide a one singly linked list into two sub lists of almost equal sizes).

Answer 1

This can be solved with a dynamic programming approach, which basically comes down to, for each element and value, either including or excluding that element, and looking up whether there's a subset summing to the corresponding value. More specifically, we have the following recurrence relation:

p(i, j) is True if a subset of { x1, ..., xj } sums to i and False otherwise.

p(i, j) is True if either p(i, j − 1) is True or if p(i − xj, j − 1) is True

p(i, j) is False otherwise

Then p(N/2, n) tells us whether a subset exists.

The running time is O(Nn) where n is the number of elements in the input set and N is the sum of elements in the input set.

The "approximate" greedy approach (doesn't necessarily find an equal-sum partition) is pretty straight-forward - it just involves putting each element in the set with the smallest sum. Here's the pseudo-code:

INPUT:  A list of integers S
OUTPUT: An attempt at a partition of  S into two sets of equal sum
1  function find_partition( S ):
2     A ← {}
3     B ← {}
4     sort  S in descending order
5     for i in S:
6        if sum(A) <= sum(B)
7           add element i to set A
8        else
9           add element i to set B
10    return {A, B}

The running time is O(n log n).