1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ What kind of answer are you looking for? A formula? An algorithm? Also, how is the set $S$ given to you? $\endgroup$ – Yuval Filmus Sep 10 '14 at 23:00
  • $\begingroup$ Preferably an algorithm, and I've already put S into an array of numbers. $\endgroup$ – user165680 Sep 11 '14 at 2:14
  • $\begingroup$ You are looking for partitions/compositions of integers, both well-studied notions. Whether anything is known depends on $S$. $\endgroup$ – Raphael Sep 11 '14 at 8:16
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ FWIW, the problem may be easy for many $S$; there may even be infinite easy subclasses. $\endgroup$ – Raphael Sep 11 '14 at 8:17
  • $\begingroup$ @Raphael, absolutely! (That's pretty much always true for NP-hard problems.) But I'll add that to the answer. $\endgroup$ – D.W. Sep 11 '14 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.