Can you give me any hints, how to do this prog at least in minimally optimal way? I want to do this program alone, but without any hints a feel I will give up.

You should use DP (Dynamic Programming) for calculating results for different Summs and Number length.
But its better to use 2 tables.
But its another hint. =)

I didn't use DP at all and got AC in 0.14 sec.
The only hint you should take into account is:

The number of different permutations of n objects, where there are n1 indistinguishable objects of style 1, n2 indistinguishable objects of style 2, ..., and nk indistinguishable objects of style k, is

n!/ (n1! * n2! * ... nk!);

(c) regentsprep.org