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:
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
If I need to break up
20 into 3 power of 2s, I could have
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?