Find all Combinations of 1 and 2 which sums up to k.

Question

I have two numbers $1$ and $2$. I have to print all ordered combinations which sums up to $k$.

For example:

$k=1$ Its only $1$.

$k=2$ It's ${1,1},{2}$.

$k=3$ Its ${1,1,1},{1,2},{2,1}$

What could be the algorithm to print these combinations ?

I could easily find the number of ways using Dynamic Programming like $f[n]=f[n-1]+f[n-2];$ where $f[0]=0,f[1]=1$ and $f[2]=2$.

Hence $f[3]=f[2]+f[1]=2+1=3$. But my concern is to print these combinations.

Answer 1

I am posting a recursive algorithm to print all such combinations. Hope this will be helpful.

//prints all ordered combination of 1 and 2 which sum up to n function printAll(n){ //[] is empty list print(n,[]) } function print(n,list){ //base case if(n==0){ output all the elements in list }else{ //passing a new list by appending "1" to "list" print(n-1,newlist(list,1)) if(n>=2){ //passing a new list by appending "2" to "list" print(n-2,newlist(list,2)) } } }

you will get output in this order for (n=4)

1 1 1 1

1 1 2

1 2 1

2 1 1

2 2