c - Program to disintegrate a number into fibonacci numbers -

i struggling write program in c. want disintegrate number (only if can disintegrated) smaller numbers can fibonacci numbers. example :

if have number n = 20 output should 1,1,2,3,5,8 when add these smaller fibonacci numbers gives me number 20.

it can reduced subset-sum problem, set fibonacci numbers smaller/equals given number.

first generate numbers smaller/equals given number n. c-like pseudo code:

int = 1; int* arr = //sufficiently large array arr[0] = arr[1] = 1; while (arr[i] <= n) {      i++;     arr[i] = arr[i-1] + arr[i-2]; } 

after this, have arr contains "candidates", , need invoke subset-sum algorithm solve it, using following recursive calls

d(x,i) = false   x<0 d(0,i) = true d(x,0) = false   x != 0 d(x,i) = d(x,i-1) or d(x-arr[i]-1,i) 

you later, need retrace steps , find out actual number used dp:

pseudo code:

x = n; = number_of_candidates; while (i>0) {    if (x >= arr[i] && dp[i][x-arr[i]]) {          //arr[i] in solution, add         x = x-arr[i];     }     i--; //do both cases, successful 'if' or not. } 

total complexity of answer o(nlogn), , bottleneck dp solution.
note number of "candidates" in o(logn), since ith fibonacci number in o(phi^i).