What is the computational complexity of k bit subset sum problem?
I'm assuming that when $k=1$, the $k$th bit is the LSB.

If $b = 0$ then the answer is always positive, since you can take the sum of the empty subset.

If $b = 1$ and one of the numbers has its $k$th bit equal to $1$ then the answer is positive, so we can assume that all $k$th bits are equal to $0$. Reduce all numbers modulo $2^k$. Since originally the $k$th bits were $0$, all numbers are less than $2^{k-1}$. If the sum of all numbers is less than $2^{k-1}$, then clearly the answer is negative. If the sum of all numbers is at least $2^{k-1}$, arrange them in some arbitrary order $x_1,x_2,\ldots$, and sum them one by one until reaching the first sum $s_i = x_1 + \cdots + x_i$ which is at least $2^{k-1}$. Since $s_{i-1} &lt; 2^{k-1}$ and $x_i &lt; 2^{k-1}$, we see that $s_i &lt; 2^k$. Thus the $k$th bit of $s_i$ is $1$. Hence the answer is positive.

Summarizing, here is our algorithm:


If $b = 0$, answer True.
If $b = 1$ and there exists a number whose $k$th bit is $1$, answer True.
If $b = 1$ and all $k$th bits are $0$, reduce the input modulo $2^k$, and answer True if the sum of all reduced numbers is at least $2^{k-1}$.