问题描述:

Here I am just putting python code.

 Rec(Arr,N,K,X) :

if(X==0 and K==0):

return 1

elif(X<=0 or K<=0 or N<0):

return 0

else :

return Rec(Arr,N-1,K,X)+Rec(Arr,N,K-1,X-Arr[N])

Provided that all element of Arr are distinct,this conclude that all sub problems are non-overlapping(just took an small case, do it manually)

Please Evaluate Time Complexity in terms of N,K,X.

Thanks for reading this question...

网友答案:

Basically this problem is regarded as depth first search of a binary tree whose height is bounded by max(N,K). So order of time complexity is bounded by 2^max(N,K). And then X and Arr might reduce this time complexity. But it is unclear because it depend on the values of Arr and X. (For example if Arr=[inf,...,inf], the time complexity will be N.)

相关阅读:
Top