Recursion vs bitmasking for getting all combinations of vector elements

Question

While practicing for programming competitions (like ACM, Code Jam, etc) I've met some problems that require me to generate all possible combinations of some vector elements.

Let's say that I have the vector {1,2,3}, I'd need to generate the following combinations (order is not important) :

1
2
3
1 2
1 3
2 3
1 2 3

So far I've done it with the following code :

void getCombinations(int a)
{
    printCombination();
    for(int j=a;j<vec.size();j++)
    {
        combination.pb(vec.at(j));
        getCombinations(j+1);
        combination.pop_back();
    }
}

Calling getCombinations(0); does the job for me. But is there a better (faster) way? I've recently heard of bitmasking. As I understood it's simply for all numbers between 1 and 2^N-1 I turn that number into a binary where the 1s and 0s would represent whether or not that element is included in the combinations.

How do I implement this efficiently though? If I turn every number into binary the standard way (by dividing with 2 all the time) and then check all the digits, it seems to waste a lot of time. Is there any faster way? Should I keep on using the recursion (unless I run into some big numbers where recursion can't do the job (stack limit))?

Answer 1

The number of combinations you can get is 2^n, where n is the number of your elements. You can interpret every integer from 0 to 2^n -1 as a mask. In your example (elements 1, 2, 3) you have 3 elements and the masks would therefore be 000, 001, 010, 011, 100, 101, 110, and 111. Let every place in the mask represent one of your elements. For place that has a 1, take the corresponding element, otherwise if the place contains a 0, leave the element out. For example the the number 5 would be the mask 101 and it would generate this combination: 1, 3.

If you want to have a fast and relatively short code for it, you could do it like this:

#include <cstdio>
#include <vector>

using namespace std;

int main(){

    vector<int> elements;

    elements.push_back(1);
    elements.push_back(2);
    elements.push_back(3);

    //  1<<n is essentially pow(2, n), but much faster and only for integers
    //  the iterator i will be our mask i.e. its binary form will tell us which elements to use and which not
    for (int i=0;i<(1<<elements.size());++i){
        printf("Combination #%d:", i+1);
        for (int j=0;j<elements.size();++j){
            //  1<<j shifts the 1 for j places and then we check j-th binary digit of i
            if (i&(1<<j)){
                printf(" %d", elements[j]);
            }
        }
        printf("\n");
    }

    return 0;
}