arrays - How to divide a set into two subsets such that difference between the sum of numbers in two sets is minimal?

Question

Given a set of numbers, divide the numbers into two subsets such that difference between the sum of numbers in two subsets is minimal.

This is the idea that I have, but I am not sure if this is a correct solution:

1. Sort the array
2. Take the first 2 elements. Consider them as 2 sets (each having 1 element)
3. Take the next element from the array.
4. Decide in which set should this element go (by computing the sum => it should be minimum)
5. Repeat

Is this the correct solution? Can we do better?

Answer 1

The decision version of the problem you are describing is an NP-complete problem and it is called the partition problem. There are a number of approximations which provide, in many cases, optimal or, at least, good enough solutions.

The simple algorithm you described is a way playground kids would pick teams. This greedy algorithm performs remarkably well if the numbers in the set are of similar orders of magnitude.

The article The Easiest Hardest Problem, by American Scientist, gives an excellent analysis of the problem. You should go through and read it!