This is much more an algorithm/proof question than programming/implementation, so apologies if StackOverflow is not the right place for it.
As for the problem:
suppose that we have a set of numbers, and every number must be a positive integer and a power of 2. So for example, maybe we have {1, 1, 2, 4, 8, 8, 8, 8, 128}. We want to partition the set in to A and B, where every element must be in exactly A or B, such that the sum of A's elements equals the sum of B's elements. Is there a polynomial time algorithm for this situation which will always either
A and B such that their sums are equal? If there's not a polynomial time algorithm, of course, I'd love to know some direction for the proof of that (i.e., by showing equivalence to another NP-hard problem).
I know that there are a few problems that could help, and for context, I'll summarize them here:
sum(A) = sum(B).Any help is greatly appreciated. Thanks!
One way of looking at this is to say that you are trying to express a target number, which is total/2, as a sum of the numbers provided. This is really just the problem of making change.
Here is a useful lemma: if you have a collection of coins whose values are all powers of two of value <= 2^k, then you can either make exactly 2^k or you cannot make any number as large, or larger, than 2^k. To see this, take all your coins and, if you have more than one coin of the same value, stick those two coins together to make a coin of the next highest value until you run out of coins or reach 2^k. If you reach 2^k you are done. If you run out, you have a collection of single coins of a variety of values, which are still powers of two, all less than 2^k, and only one per different value, so the result cannot add to more than 2^k-1.
Now to make change of your target value, treat your numbers as coins and repeatedly put aside the largest coin available which is no more than the difference between the value you have so far and the target value.
If you reach the target value the problem is solved. If not, did you miss the right answer? You started with the largest value coins. Look for your first mistake - you took a coin of size 2^k and there is some way to make up the remaining sum that does not include this coin of size 2^k. But this magic way is a way to make up change of more than 2^k using coins of value of no more than 2^k. So somewhere within this right answer there is a set of coins that adds up to exactly 2^k. Take this right answer and remove the coins that add up to 2^k and replace it with the coin for 2^k that you used and you get another right answer - so you were right after all and if you can get any solution you can get it by repeatedly using the largest coin (number) available less than the distance to the target value.
Sanity check - look at the reduction for subset sum given in http://cs.mcgill.ca/~lyepre/pdf/assignment2-solutions/subsetSumNPCompleteness.pdf and notice that it requires numbers which are not exact powers of two, so what I propose here, which is proved to work only when the numbers are powers of two, does not claim to be solving an NP-complete problem in polynomial time.