# Make Change in Linear Time

The question is motivated by this post on StackOverflow.

Given an integer $$n$$ and a finite list of distinct positive integers $$ds$$, let $$f(n, ds)$$ denote the number of ways $$n$$ can be expressed as a sum of elements of $$ds$$ up to order. Sometimes $$f(n, ds)$$ is referred to as the number of ways to make change of $$n$$ in terms of coins with denominations $$ds$$. For example:

• $$f(1, [1]) = 1$$
• $$f(2, [1, 2]) = 2$$
• $$f(100, [1, 2]) = 51$$
• $$f(5, [1, 2, 5]) = 4$$
• $$f(27, [1, 5, 10]) = 12$$
• $$f(7, [3, 5]) = 0$$

Question: is it possible to compute $$f(n, ds)$$ in $$O(\operatorname{length}(ds))$$ time if integer operations take constant time, e.g. $$a \bmod b$$ can be computed in $$O(1)$$?

• I think this or that could help. It seems solutions are at best in $O(n|ds|)$. – Nathaniel May 15 at 11:22
• There are "lists of integers" where the greedy algorithm can be proven optimal. en.wikipedia refers to Pearson, David: A polynomial-time algorithm for the change-making problem, OR Letters 33 (2005). – greybeard May 15 at 15:29