Combinations

HSM Program 1.11 gives code that implements a recursive algorithm for generating all permutations of an array. A recursive algorithm for generating combinations of M elements from an array is:

Set combination to empty

Choose (M elements, from an Array)
if M == 0 then
    output the combination
else if the array has at least M elements then
        Add the first element to the combination
        Choose M-1 elements from the rest of the array
        if the array has more than M elements then
            Remove that first element that was added to the combination
            Choose M elements from the rest of the array

Implement this algorithm in C++.
Work out the space requirements for your program in terms of the array size and M. Assume that all base C++ types take one unit of memory.
Insert a step counter into the function that generates the combinations, and get the step count for array sizes 3 to 5 for all possible combinations sizes.
Bonus marks: Work out the formula for the step count (don't worry if you can't handle this, it's kinda tricky).

Combinations

Answer