###### Books / Introduction to Recursion and Backtracking / Chapter 5

# Recursive Algorithms - Choosing k Out of n Objects

A well-known and common combinatorial (counting) problem is how many distinct ways there are to pick *k* objects from a collection of *n* distinct objects. For example, if I want to pick 10 students in the class of 30, how many different sets of 10 students can I pick? I do not care about the order of their names, just who is in the set. Let *c(n, k)* represent the number of distinct sets of *k* objects out of a collection of *n* objects.

The solution can be difficult to find with a straight-forward attack, but a recursive solution is quite simple. Let me rephrase the problem using the students in the class. Suppose I single out one student, say student *X*. Then there are two possibilities: either *X* is in the group *I* choose or *X* is not in the group.

How many solutions are there with *X* in the group? Since *X* is in the group, I need to pick *k-1* other students from the remaining *n-1* students in the class. Therefore, there are *c(n-1, k-1)* sets that contain student X.

What about those that do not contain X? I need to pick *k* students out of the remaining *n-1* students in the class, so there are *c(n-1, k)* sets.

It follows that: \(c(n, k)=c(n-1, k-1)+c(n-1, k)\)

when *n*` is large enough. Of course there are no ways to form groups of size *k* if *k>n*, so *c(n, k)=0* if *k>n*. If *k=n*, then there is only one possible group, namely the whole class, so *c(n, k)=1* if *k=n*. And if *k=0*, then there is just a single group consisting of no students, so *c(n, k)=1* when *k=0*. In all other cases, the recursive definition applies. Therefore the recursive definition with its base cases, is:

Once again it is easy to write a function that computes this recursively by applying the definition:

```
int combinations(int n, int k) {
if (k == 0 || k == n)
return 1;
else if (k > n)
return 0;
else
return combinations(n - 1, k - 1) + combinations(n - 1, k);
}
```

The interesting question is how to show that this always terminates. In each recursive call, n is diminished.

In some, k is not diminished. Therefore, eventually either k >= n or k = 0. In any case, this is again a very inefficient way to compute c(n,k) and it should not be used.