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.