I\'m writing an algorithm to solve a research problem involving searching for nu
ID: 652211 • Letter: I
Question
I'm writing an algorithm to solve a research problem involving searching for numbers on very large arrays.
I encountered a sub-problem that requires me to break up sums of numbers which are power of 2, i.e. how to find combinations of these numbers that sum up to a certain value. The sum and the combination size are given. Also only 4 power of 2s can be present in a combination: 2,4,8,16.
Lets suppose I have a sum of 8 and I need to break up into a set of 3 numbers. The result would invariably be [2,2,4].
If I need to break up 20 into 3 power of 2s, I could have [2,2,16] or [4,8,8].
Naturally larger sets will result in many possible combinations.
My aim is to write an algorithm that obtains all possible combinations as efficiently as possible. I'm not looking for the algorithm itself, but some leads into how to partition the number. What are some properties of power of 2s that I need to use to partition a sum into a possible combination?
Explanation / Answer
Look at the binary representation of the sum. Each 1 in that representation represents a power of two that has to be included as a summand, either directly or indirectly.
If the number of 1s in that representation is greater than the number of summands, there is no solution, if it is equal, there is exactly one solution, and if it is smaller, things get interesting.
The basic property you'll want to exploit in the last case is that you can represent any power of two as once that power, or twice the next smaller power, or 4 times the one after that and so on.
I think this approach can lead to an efficient algorithm. (But I did not follow it through myself, so no guarantees.)