Partition Problem

general
1

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

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

2

I think your algorithm will not return correct result for the following array: 5 5 4 3 3. The correct answer should be 0, since the array can be divided into 2 equal groups: 5 5 & 4 3 3, but your algorithm returns 2 ( or -2). Your solution is a greedy one and will not work for this problem.

1 Like
3

Exactly what I needed! I have been struggling for weeks to generate such a test case. Thank you sooo much @gvaibhav21

4

you’re welcome :slight_smile: