Recursive Combination Algorithm Implementation in C++

The combination is a frequently-used technique that choose a number of items from a whole data set (sequence is not important). For example, to choose 2 items from 3, we have:

1 2
1 3
2 3

So please bear in mind that sequence doesn’t matter, so 1 2 is the same as 2 1.

The total number of combination of choosing m items from n can be computed by.

For example, meaning that there are 10 different solutions choosing 3 items from 5.

So, how do we express this in recursive relations?

For the first item, we can pick from item n to m and then we can choose m-1 items from the n-1 items. Let’s make it in C/C++ code. We need to store the sequence in a array, which can be static or dynamic created.

/* HelloACM.com */
#include <iostream>
using namespace std;

void comb(int n, int r, int *arr, int sz) {
    for (int i = n; i >= r; i --) {
        // choose the first element
        arr[r - 1] = i;
        if (r > 1) { // if still needs to choose
            // recursive into smaller problem
            comb(i - 1, r - 1, arr, sz);
        } else {
            // print out one solution
            for (int i = 0; i < sz; i ++) {
                cout << arr[i] << " ";
            }
            cout << endl;
        }
    }
}

int main() {
    const int N = 5;
    const int M = 3;
    int *arr = new int[M];
    comb(N, M, arr, M);
    delete []arr;
    return 0;
}

The above is simple and handy if you want to list all combinations given n and m. Of course, when the values are large enough, a possible stack overflow will occur when recursion depths become large.

You may be interested to read this also: The Combination Function and Iterator using Depth First Search Algorithm

Also, we can use the bitmasking algorithm to do the combination: Using Bitmasking Algorithm to Compute the Combinations of an Array

Also, we can use the backtracking to implement a iterative combination – as described in this post.

–EOF (The Ultimate Computing & Technology Blog) —