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$
3
  • 2
    $\begingroup$ What kind of answer are you looking for? A formula? An algorithm? Also, how is the set $S$ given to you? $\endgroup$ Sep 10, 2014 at 23:00
  • $\begingroup$ Preferably an algorithm, and I've already put S into an array of numbers. $\endgroup$ Sep 11, 2014 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, 2014 at 8:16

1 Answer 1

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$
2
  • 1
    $\begingroup$ FWIW, the problem may be easy for many $S$; there may even be infinite easy subclasses. $\endgroup$
    – Raphael
    Sep 11, 2014 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, 2014 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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