Number of solutions to $x_0+x_1+\ldots+ x_n=m$ where $x_i$ take specific integer values 
Let $x_i\in \{0,\pm 2^i\}$. Fix $m\in \mathbb{Z}$. I am trying to see if we can write all possible combinations of values for $x_0,x_1,\ldots,x_n$ such that
$$
x_0+x_1+\ldots+x_n = m \tag{1}
$$

First of all I'm not sure how to find the set of possible values for $x_0+x_1+\ldots+x_n$. Nevertheless, given $m\in \mathbb{Z}^+$, I know (from several examples on MSE) how to find the number of solutions to $(1)$ where $x_i$ are positive integers i.e. examples where $x_i$ take values from the same set. But given the set of values $x_i$ can take, from the example above, I'm not sure how to approach this problem. Any ideas?
 A: The number of solutions follow this recurrence:
$$h_{n,m}=h_{n-1,m-2^n}+h_{n-1,m}+h_{n-1,m+2^n}.$$
The computation of the first values gives the following table (the negative values are omitted to save space, the histograms are symmetrical).

I am afraid that a pattern will be hard to find. Notice, anyway, that all columns follow an arithmetic progression so that knowing two values in a column gives the whole column.
A: Either $m=0$ and you have only 1 solution or you have infinitely many.
You can prove the $m=0$ case by using the following inequality: $\sum_{k=0}^{n-1} 2^k = 2^n-1 < 2^n$
For $m\ne0$ case, assume there is a solution $x^*$ with $\nu = \max_i\{i : x_i^* \ne 0\}$ (There will always be a finite solution of maximum $\text{ceil} (\log_2(m))$ non-zero terms). Then you can use $x^*_\nu = x^*_\nu \cdot (2-1)$ to see that if you change the solution to have $x_\nu \to -x_\nu$ and add a new term $x_{\nu+1}\to2x_\nu$, then you have another solution. You can iterate this method as many times as you want and you still get a correct soltuion.
Example: $m=1$
1-st solution: $x_0 = 1, x_n=0 (\forall n\ge1)$
2-nd solution: $x_0 = -1, x_1 = 2, x_n=0 (\forall n\ge2)$
3-rd solution: $x_0 = -1, x_1 = -2, x_2 = 4, x_n=0 (\forall n\ge3)$
...
A: This is just to address Yorch comment (and using Yves notation), the number is equal to
$$h_{n,m}=\sum _{\substack{0\leq a,b\leq 2^{n+1}-1\\a+b=m+2^{n+1}-1}}\left (\frac{1-\sqrt{3}i}{2}\right )^{-s_2(a)}\left (\frac{1+\sqrt{3}i}{2}\right )^{-s_2(b)},$$
where $s_2(n)$ is the number of $1$'s in the binary expansion of $n$.
This you get when you try to find $$[x^{m}]\prod _{i=0}^n\left (1+x^{2^i}+x^{-2^i}\right ).$$
Edit:

Notice that in the above expression, using the notation given in Yves answer, when either $a$ or $b$ are $\geq 2^{n}$ one has that the other is less than that. Say $a\geq 2^{n},$ then $a'=a-2^{n}$ gives  $s_2(a)=1+s_2(a')$ and the condition in the sum is the same as for $h_{n-1,m}$ so we get $(2/(1-\sqrt{3}i)+2/(1+\sqrt{3}i))h_{n-1,m}=h_{n-1,m}.$ This implies then that
$$h_{n,m}=h_{n-1,m}+\sum _{\substack{0\leq a,b\leq 2^{n}-1\\a+b=-m+2^{n+1}-1}}\left (\frac{1-\sqrt{3}i}{2}\right )^{-s_2(a)}\left (\frac{1+\sqrt{3}i}{2}\right )^{-s_2(b)}.$$
Apparently, this is constant on $n$ and from the data it seems that it is actually $a(m)$ the Stern's diatomic series (see OEIS). This sequence has recurrence $a(2n)=a(n),a(2n+1)=a(n)+a(n+1).$ Giving you that $h_{n,m}=h_{n-1,m}+a(m)$ for $m<2^n$ and $h_{n,m}=h_{n-1,m-2^n}$ otherwise.
