Greedy Heuristics with an Altered Subset Sum/Partition Problem

Question

Say we have a constant-time function that accepts some integer set. The function outputs True if we can split the integers into two subsets of an equal sum. If we can't partition the integers given, the function outputs False.

Suppose we can use this function at any time, with any set of integers. Can we make a greedy algorithm using this function that will output one of the specific subsets that sum to half of a particular positive integer set?

The heart of the question: If we know at any time the boolean result of canPartition() on any set of integers, can we greedily use that to output the specific values of a partition?

Answer 1

Suppose that a set $S$ of size more than 2 can be partitioned into two subsets of identical sum. One of these subsets contains at least two elements. If you merge these two elements (that is, replace them with a new element whose value is the sum of the values of the two elements), then the partition property still holds; and furthermore, given a partition of the new set, you can construct a partition of the original set.

You can find two elements in the same part by considering any three elements – two of them will be in the same part and so can be merged. This gives an algorithm for your problem with $O(n)$ oracle calls, where $n$ is the number of elements in the original set.