Phil15 - 1 year ago 87

C++ 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.

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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)
```

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**