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?
Are all elements distinct ?
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