Given a multiset $X=\{x_1,\dots,x_n\}$ where every element $w_i$ is a power of two, and given an integer $M$, I'd like to determine if there is any subset of $X$ that sums to $M$.
(This question is based on a previous question about the subset problem where every number in the set is a multiple of two, but this time $X$ consists only of powers of two.)
Can we find an efficient algorithm for this problem? Could we make it any better than standard algorithms for subset sum or knapsack?
First, look at the bits that are set in $M$ and write it as $M = m_1+m_2+\dots$ where each $m_i$ is a power of two and such that $m_1$ is the smallest power of two, and so on.
If the numbers $x_i \in X$ are distinct powers of two and you can use each one zero or one times, the problem is trivial: If all $m_i$ are found in $X$, then $M$ can be formed by them, otherwise it can't. This is because missing powers of two can't be formed by a) any combination of larger powers of two or b) distinct smaller powers of two.
If the numbers $x_i$ aren't guaranteed to be distinct, it's a bit more complex. Missing powers of two still can't be formed by larger powers of two, but they can be formed by non-distinct smaller powers of two.
Let's look at how smaller powers of two can form larger powers of two. If you have powers of two $A = [a_1, \dots, a_n]$ that are smaller than a power of two $N$, and $S=\sum_{i=0}^n a_i$, then $N$ can be formed by them iff $S \ge N$. Let $b$ be the smallest power of two in $A$ and $c$ its number of occurences in $A$. If $c$ is odd, one $a_i=b$ can't combine with anything to form a higher power of two and the corresponding bit will be set in $S$. The others can be replaced with $\lfloor \frac{c}{2} \rfloor$ copies of the number $2b$ in $A$. If we continue this with higher powers of two until we get to $N$, we find that we can form $\lfloor \frac{S}{N} \rfloor$ copies of $N$ with $A$.
So, start with $m_1$. If it's found in $X$, we remove it and move to the next power of two. If it's not, we calculate the sum $S$ of all $x_i$ smaller than $m_1$ and remove them from $X$. If $S \lt N$, then $M$ can't be formed by $X$. Otherwise, we add $\lfloor \frac{S}{m_1} \rfloor - 1$ copies of $m_1$ to $X$ and continue in the same manner with the next smallest power of two in $M$.
