Generăm toate variantele posibile ale vectorului <tex>x</tex> pentru care <tex>x[1] + x[2] + ... + x[N] = K</tex>. Această soluţie obţine 0 sau 10 puncte în funcţie de implementarea backtrackingului, care ar avea complexitatea <tex> O(K^N) </tex> amortizat.

h2. $Soluţie N^3^ - 50 puncte$

h2. $Soluţie N*K^2^ - 50 puncte$

Această soluţie presupune tehnica programării dinamice. Vom folosi matricea $dp[n][k]$, pentru care:

Observatie: <tex>$dp[i][0]=1$</tex>,  <tex>1<=i<=n</tex>, ca să ne iasă calculele :)

Voi exemplifica explicaţia cu cod în **limbajul C++**

Voi exemplifica explicaţia cu cod în **limbajul C++**
 
==code(c++) |
dp[1][0]=1;
    for(j=1; j<=k; j++)
        dp[1][j]=(1LL*j*hazard[1])%MOD;
    for(i=2; i<=n; i++)
    {
        dp[i][0]=1;
        for(j=1; j<=k; j++)
        {
            for(x=0; x<=j-1; x++)
                dp[i][j]=(dp[i][j]+1LL*dp[i-1][x]*(j-x)*hazard[i])%MOD;
            dp[i][j]=(dp[i][j]+dp[i-1][j])%MOD;
        }
    }
==