Hello All,

I had this question asked to me in one of the interviews and I wasn't able to figure it out.I need to write a method CountUniqueSequences(int sum) which returns the number of unique sequences that consist of only 1's and 2's and have an element summation equal to a given N.

For example, below are all unique sequences consisting of 1's and 2's with element summation of N=4:

1 1 1 1

1 1 2

1 2 1

2 1 1

2 2

So, CountUniqueSequences(4) should return 5.

I figured out that the frequency of occurrences of 1 in case of even nos. consist of only even nos. and in case of odd nos. consist of only odd nos.Correspondingly, the frequency of occurrence of 2 gets incremented each time the frequency of occurrence of 1 decreases.

For instance,to obtain 4:

1 can be used 2 times or 4 times and 2 can be used 1 time or 0 time.

To obtain 5: 1 can be used 1,3 or 5 times and correspondingly 2 can be used 2,1 or 0 times.

Although,it's not required in the problem I know that I can permute the number to obtain all possibilities but I do not know how to form a number.

Any suggestions would be greatly appreciated.