Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Using an infinite supply of integers of a set S, how many ways are there to reach a sum of n?
Clarification: The Integers are arbitrary, positive, and may not include 1.
At first I thought it was the coin changing problem without pennies, but it's not because the order is important so coin changing will always be less.
It's also like Leonardo's Leaps but with arbitrary leap sizes, and again possibly without a leap of 1.
This is NP-hard, by reduction from the partition problem.
Consider the decision problem version of your problem: given $S,n$, is there at least one way to reach a sum of $n$ using the integers from $S$ (possibly multiple times).
Suppose I have a partition instance, a set $T$ where I want to know whether it can be partitioned into $T_1,T_2$ such that the sum of $T_1$ equals the sum of $T_2$. Let $c$ be a very large constant, and define $S=\{t+c : t \in T\}$ and $n=(m+|T|c)/2$ where $m$ is the sum of all of the numbers in $T$.
Then the answer to the decision problem is yes if and only if the answer to the original partition problem was yes.
You should be able to fill in the details from here (including, in particular, how to choose the constant $c$, based upon $T$).
See also https://cstheory.stackexchange.com/q/19758/5038.
Of course, the problem may still be easy for many $S$; there may even be infinite easy subclasses. See also Dealing with intractability: NP-complete problems for more on strategies for what to do, when you have a problem that is NP-hard but you still have to solve it.
