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