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.
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]
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?