Let Me Count the Ways

Design a hardware module for the Let Me Count the Ways problem.

Given a target sum n and a list of coin denominations a, count how many unordered combinations of those denominations add up to exactly n.

Each denomination may be used any number of times. Repeated values in a do not create new denomination types.

Hardware I/O Encoding

• n is a scalar unsigned 5-bit integer
• a is a one-dimensional stream of unsigned 5-bit integers
• each streamed value is one available coin denomination
• the output is one unsigned 32-bit integer
• the output value is the number of unordered ways to make exactly n

Examples

Example 1

• input n = 4, a = [1, 2, 3]
• output: 4

The four combinations are 1+1+1+1, 1+1+2, 1+3, and 2+2.

Example 2

• input n = 5, a = [2, 4]
• output: 0

No combination of 2 and 4 sums to 5.

Example 3

• input n = 6, a = [1, 1, 3, 4]
• output: 4

The duplicate 1 does not change the answer. The combinations are 1+1+1+1+1+1, 1+1+1+3, 1+1+4, and 3+3.

Source: inspired by the classic coin-change problem often titled "Let Me Count the Ways"