Can you explain this recursive "n choose k" code to me?

Question

Here is the code to a subset problem with arguments n and k. n represents the total number of students and k represents the amount of the students I want to get out of n. The code attempts to give the number of possible combinations of pulling k number of students out of n number of students. ``` def subset(n, k): if k == 0: return 1 if n == k: return 1 else: return subset(n-1, k-1) + subset(n-1, k) ``` I understand the first part of the recursive call, but I'm having trouble understanding the + subset(n-1, k) part. Can anyone explain this to me?

Accepted Answer

The recursion is based on a simple observation, for which I will give a combinatorial argument, as to why it is true, rather than a mathematical proof through formulae.

Whenever you choose `k` elements out of `n`, there are two cases:

- You choose element `#n`

- You don't choose element `#n`

Since these events are mutually exclusive, the total amount of combinations is given by the amount of combinations when choosing `#n`, and those when you don't choose `#n`.

Choosing element `#n`

Since we have already chosen one element, we need only choose another `k-1` elements. Also, since we have decided upon one element – as to whether it is included or not – already, we only need to consider the remaining `n-1` elements.

Thus, the amount of combinations for choosing element `#n` is given by

```
    subset(n - 1, k - 1)
```

Not choosing element `#n`

There are still `k` elements to choose, but since we have already made up our mind about element `#n`, there remain only `n - 1` elements to choose from. Thus:

```
    subset(n - 1, k)
```

The base case

The recursion uses the fact, that we can usually differentiate between two situations, solutions where element `n` is part of that solution, and those where it is not.

However, such a distinction can not always be made:

- When choosing all elements (corresponding to case `n == k` in code below)

- or when choosing no elements at all (corresponding to case `k == 0` in code below)

In these cases, there is only exactly one solution, hence

```
if k == 0:
    return 1
if n == k:
    return 1
```

Ensuring it works

To do that, we need to convince ourselves (or prove) that the base case is always hit at some point.

Let us assume, that `n < k` at some point. Since per our assumption, `n` was originally greater or equal to `k`, there must have been some point where `n = k`, because `n` and `k` decrease in unison or only `n` decreases by one, i.e. it follows

This implies, that there must have been a call to `subset(n - 1, k)` for it to happen, that `n` decreases below `k`. However, this is not possible since we have a base case on `n = k` where we return a constant `1`.

We conclude that either `n` decreases at some point such that `n = k`, or decrease in unison exactly `k` times such that `k = 0`.

Thus, the base case works.

Can you explain this recursive "n choose k" code to me?

Solution

Problem