I came across the Partition Problem recently which can be manipulated to return the lowest difference between the 2 sets the array is divided into.

http://en.wikipedia.org/wiki/Partition_problem

Although I know there is some flaw somewhere, this is the idea I got and I am unable to find that flaw.

Let’s say we have an int array A with N elements indexed from 0 to N-1

1)Sort the array A in descending order

- Set lowest_difference=A[N-1]

Now,

** for i = N-2 to 0**

if lowest_difference > 0

lowest_difference = lowest _difference - A[i]

if lowest_difference <= 0

lowest_difference = lowest _difference + A[i]

So finally, the answer is absolute value of lowest_difference

Could someone please contradict this algorithm with a case where the minimum difference is not returned?