Print all subsets of given size of a set

Generate all possible subset of size r of given array with distinct elements.

Examples:

Input  : arr[] = {1, 2, 3, 4}
            r = 2
Output :  1 2
          1 3
          1 4
          2 3
          2 4
          3 4

Input  : arr[] = {10, 20, 30, 40, 50}
            r = 3
Output : 10 20 30 
         10 20 40 
         10 20 50 
         10 30 40 
         10 30 50 
         10 40 50 
         20 30 40 
         20 30 50 
         20 40 50 
         30 40 50 

The idea here is similar to Subset Sum Problem. We one by one consider every element of input array, and recur for two cases:

1) The element is included in current combination (We put the element in data[] and increment next available index in data[])
2) The element is excluded in current combination (We do not put the element and do not change index)

When number of elements in data[] become equal to r (size of a combination), we print it.

This method is mainly based on Pascal’s Identity, i.e. ncr = n-1cr + n-1cr-1

// Program to print all combination of size r in // an array of size n #include <stdio.h> void combinationUtil(int arr[], int n, int r,                      int index, int data[], int i);    // The main function that prints all combinations of  // size r in arr[] of size n. This function mainly // uses combinationUtil() void printCombination(int arr[], int n, int r) {     // A temporary array to store all combination     // one by one     int data[r];        // Print all combination using temprary array 'data[]'     combinationUtil(arr, n, r, 0, data, 0); }    /* arr[]  ---> Input Array    n      ---> Size of input array    r      ---> Size of a combination to be printed    index  ---> Current index in data[]    data[] ---> Temporary array to store current combination    i      ---> index of current element in arr[]     */ void combinationUtil(int arr[], int n, int r, int index,                      int data[], int i) {     // Current cobination is ready, print it     if (index == r) {         for (int j = 0; j < r; j++)             printf("%d ", data[j]);         printf("\n");         return;     }        // When no more elements are there to put in data[]     if (i >= n)         return;        // current is included, put next at next location     data[index] = arr[i];     combinationUtil(arr, n, r, index + 1, data, i + 1);        // current is excluded, replace it with next     // (Note that i+1 is passed, but index is not     // changed)     combinationUtil(arr, n, r, index, data, i + 1); }    // Driver program to test above functions int main() {     int arr[] = { 10, 20, 30, 40, 50 };     int r = 3;     int n = sizeof(arr) / sizeof(arr[0]);     printCombination(arr, n, r);     return 0; }

Output:

10 20 30 
10 20 40 
10 20 50 
10 30 40 
10 30 50 
10 40 50 
20 30 40 
20 30 50 
20 40 50 
30 40 50