How this works: CodeWars

I came across one task on CodeWars. Having failed to solve it, I decided to look at the solutions of those who had already passed. As befits a beginner, I didn’t understand anything. Chat-GPT is inconsistent when asking for an explanation. Help me understand what's going on here.

    def outcome(n, s, k):
        from math import comb
        if not k: return 1
        if not n or k < n: return 0
        return sum((-1) ** i * comb(n, i) * comb(k - s * i - 1, k - s * i - n) for i in range((k - n) // s + 1))

DESCRIPTION:

You have n dices each one having s sides numbered from 1 to s. How many outcomes add up to a specified number k?

For example if we roll four normal six-sided dices we have four outcomes that add up to 5.

(1, 1, 1, 2)
(1, 1, 2, 1)
(1, 2, 1, 1)
(2, 1, 1, 1)

There are 100 random tests with:

0 <= n <= 10
1 <= s <= 20
0 <= k <= n * s

Notes:

there is always exactly 1 case to reach k = 0 regardless of the number of dice you have without any dice, it's not possible to reach any positive k. Initially, I thought of solving the exercise using recursion but evenly. Then I looked for analogues in the forums but again failed.

Solution

Just for you interest, it is possible to do this recursively. It is rahter simple actually:

def outcome(n, s, k):
    dp = [[0] * (k+1) for _ in range(n+1)]
    dp[0][0] = 1  

    for i in range(1, n+1):
        for j in range(1, k+1):
            for x in range(1, min(s, j)+1):
                dp[i][j] += dp[i-1][j-x]

    return dp[n][k]

As an example:

n = 4
s = 6
k = 5
print(outcome(n, s, k))

returns 4.

I think the recursive approach explain better what is going on: First you create a 2d-array dp (of dimensions (n+1) x (k+1) to store the number of outcomes for each possible sum using i dice. This space is used to account for the base cases, when the number of dice or the target sum is 0. Set dp[0][0] = 1 for the base case, which is when there's exactly 1 way to get a sum of 0 with 0 dice. Then, loop through the number of dices and loop also through all targets from 1 to k. For each target sum j, consider all possible outcomes of rolling the current die, represented by the variable x. Iterate over x from 1 to min(s, j). The min(s, j) ensures that you don't consider outcomes higher than the number of sides s or the current target sum j. Finally, for each outcome x, add the number of outcomes from the previous number of dice (i-1) and the remaining target sum (j-x) to the current cell dp[i][j].