Given an integer n, return the number of ways it can be represented as a sum of 1s and 2s

Question

For example:

5 = 1+1+1+1+1

5 = 1+1+1+2

5 = 1+1+2+1

5 = 1+2+1+1

5 = 2+1+1+1


5 = 1+2+2

5 = 2+2+1

5 = 2+1+2

Can anyone give a hint for a pseudo code on how this can be done please. Honestly have no clue how to even start. Also this looks like an exponential problem can it be done in linear time?

Thank you.

Answer 1

In the example you have provided order of addends is important. (See the last two lines in your example). With this in mind, the answer seems to be related to Fibonacci numbers. Let's F(n) be the ways n can be written as 1s and 2s. Then the last addened is either 1 or 2. So F(n) = F(n-1) + F(n-2). These are the initial values:

F(1) = 1 (1 = 1)
F(2) = 2 (2 = 1 + 1, 2 = 2)

Answer 2

This is actually the (n+1)th Fibonacci number. Here's why:

Let's call f(n) the number of ways to represent n. If you have n, then you can represent it as (n-1)+1 or (n-2)+2. Thus the ways to represent it are the number of ways to represent it is f(n-1) + f(n-2). This is the same recurrence as the Fibonacci numbers. Furthermore, we see if n=1 then we have 1 way, and if n=2 then we have 2 ways. Thus the (n+1)th Fibonacci number is your answer. There are algorithms out there to compute enormous Fibonacci numbers very quickly.