Algorithm challenge: the Partition Problem

It depends on how much you want balanced partitions.

If you only expect partitions to be as evenly sized as possible, then no yes it’s wrong. But if you add in the requirements that the average item size in each partition should also be balanced then yes no it’s not wrong, it could be interesting to expect some sizes.

For instance {[2,2], [1,1,1,1]} are “sum-balanced”, but if we consider the average then the right answer should be {[2,1,1], [2,1,1]}. And even there, the test should take the list items, and sort them before comparison with the expected answer. Because some algorithms may return {[2,1,1], [1,2,1]} which is still valid.

2 Likes