Greedy Heuristics with an Altered Subset Sum/Partition Problem
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.