A friend of mine ask me yesterday a problem, however, the interesting part for me it is not his problem, but what I will ask here.

I want to know the optimal complexity of an algorithm (I mean the complexity of the more efficient algorithm) that solves the following problem:

Input: $n\in \mathbb N, h\in \mathbb N, (a_1,\ldots,a_n)\in \mathbb N^n.$

Output: Cardinality of the set $\{(j_1,\ldots,j_n)\in \mathbb N^n:\sum_{i=1}^n j_i a_i=h\}.$

Hope the question does make sense.

  • $\begingroup$ My guess is that depends on some kind of variance of the $(a_1,\ldots,a_n).$ For example, if all of them are equal the problem is trivial and it s getting more complicated when we start changing one then two etc... $\endgroup$ – user39115 Oct 1 '14 at 15:32
  • 4
    $\begingroup$ If $h$ is given in binary, the result may be exponentially large, hence you cannot do better than exponential time. If $h$ is given in unary, you can easily compute the result in polynomial time using the recurrence $S_{h,a_1,\dots,a_{n+1}}=\sum_{j\le h/a_{n+1}}S_{h-ja_{n+1},a_1,\dots,a_n}$. $\endgroup$ – Emil Jeřábek Oct 1 '14 at 15:53
  • $\begingroup$ Yes, yes, it is polynomial, but, I think there is maybe an explicit formula? $\endgroup$ – user39115 Oct 1 '14 at 17:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.