# No. of solutions of equation?

Given an equation $a_1 X_1 + a_2 X_2 + \cdots + a_n X_n = N$ where $a_1,a_2,\ldots,a_n$ are positive constants and each $X_i$ can take only two values $\{0,1\}$. $N$ is a given constant. How can we calculate the possible no of solutions of given equation ?

-
Well in general the number of solutions depends on all your parameters, but do you need bounds on the number of solutions or something? i.e. the best way to know it is to dumbly compute all possibilities... but that's just not brilliant, isn't it. – Patrick Da Silva Nov 3 '11 at 4:11
@PatrickDaSilva : "the best way to know it is to dumbly compute all possibilities..." This is not a good idea since N is very large. – code_hacker Nov 3 '11 at 4:17
So what do you need actually? Bounds? Or the exact number of solutions? That could be reaaaally hard. – Patrick Da Silva Nov 3 '11 at 4:23
I need exact number of solutions. – code_hacker Nov 3 '11 at 4:28
do you know the $a_i$? Because the answer depends a lot on them, probably more than on $N$. For example, with $a_i=2^i$ a simple reasoning shows that the answer is either $0$ or $1$, depending on which is bigger: $N$ or $2^n$. While with $a_1=1,...,a_n=1$ you will get $n$ chose $N$ solutions. And i assume all your numbers are probably integers.... – N. S. Nov 3 '11 at 4:29

This looks like the Knapsack Problem, which means there is no known general solution and there is unlikely to be one. Specifically, it is a hard problem to decide if there is even one solution. If all $a_i$ are equal, then it becomes simple.

-
So my guess that this was a very hard problem was indeed right. Thanks for the answers both of you, user981570 and Carl =) – Patrick Da Silva Nov 3 '11 at 4:44

This is counting the number of solutions to the knapsack problem. You can adapt the Dynamic Programming algorithm to do this in pseudopolynomial time. (I'm assuming the input data are integers.) Let $s[i,w]$ = # of ways to achieve the sum $w$ using only the first $i$ variables. Then $$s[0,w]=\begin{cases}1 & w=0 \\0 & w \ne 0\end{cases}$$ For $i=1\ldots n$, For $w=0\ldots N$ $$s[i,w] = s[i-1,w] + s[i-1,w-a_i]$$

-