java - Find a Number of ways to Generate a Number -

i have given fibonacci digits only , have find out numbers of ways generate number using k fibonacci numbers only.

constraints:

1<=k<=10 1<=n<=10^9 

for example:

n=14 , k=3 

there 2 ways:

(8,5,1) , (8,3,3)  

here recursive solution:

public static void num_gen(int ,long val ,int used){        if(used==0){            if(val==n) ans++;           return ;       }        if(i==fib.length) return ;        for(int j=0;j<=used;j++){            long x = j*fib[i];           if(x+val<=n){               num_gen(i+1,x+val, used-j);           }       }  } 

this solution timeout large value of n , k=10. can provide me algorithm better complexity.

this can expressed multiplying polynomials exponents fibonacci numbers.

number of factors k.

the result coefficient of member of result polynomial exponent equals n.

example: number of ways compose number 7 3 numbers each of these 3 numbers can 1,2 or 3.

(x + x² + x³)³ = x⁹ + 3x⁸ +6x⁷ + 7x⁶ + 6x⁵ + 3x⁴ + x³

result 6 since coefficient of x⁷ member of result polynomial.