generating all combinations of size r from n elements?



Can anyone tell me an efficient method and implementation of how to generate all combinations of size r from a given array of n elements?


Use recursion (backtracking).

For selecting ‘r’ elements from a set of size ‘n’, we can either select first element and then select ‘r-1’ elements from the rest of ‘n-1’ elements or we do not select first element and choose ‘r’ elements from the remaining ‘n-1’ elements. This is the combinatorial proof of the formula C(n,r) = C(n-1,r-1) + C(n-1,r)

This is also an induction formula, and as you can see, size of sub problem decreases at each step.

We can write a function which uses this algorithm to determine all the combinations of ‘r’ elements from a set of ‘n’ elements.

C++ Code : Ideone Link


Are all elements distinct ?