Unique combinations of numbers that add up to a sum

Question

I was asked this in an interview recently and got completely stumped. I know there are questions like this asked on here before but none handled the little twist thrown onto this one.

Given a number, find all possible ways you can add up to it using only the numbers 1,2,3. So for an input of 3, the output would be 4 because the combinations would be 1,1,1 and 1,2 and 2,1 and 3. I know about the coin change algorithm but it doesn't give me that permutation of 1,2 and 2,1. So I just ended up implementing the coin change algorithm and couldn't get the permutation part. Does anybody have any ideas?

Answer 1

It's a recursive problem:

take for example the possible options for 5

X X X X X
1 X X X X
2   X X X
3     X X

So f(5)=f(4) + f(3) + f(2)

So the generic solution is

f(1)=1
f(2)=2
f(3)=4
f(N)= f(N-1) + f(N-2) + f(N-3) for N > 3

Answer 2

To answer your question about classification of the problem it looks like dynamic programming problem to me. See following question taken from stanford.edu

1-dimensional DP Example

◮ Problem: given n, find the number of different ways to write
n as the sum of 1, 3, 4
◮ Example: for n = 5, the answer is 6
5 = 1 + 1 + 1 + 1 + 1
= 1 + 1 + 3
= 1 + 3 + 1
= 3 + 1 + 1
= 1 + 4
= 4 + 1

And here is the solution to similar problem