Print all possible combinations of r elements in a given array of size n - GeeksforGeeks

Print all possible combinations of r elements in a given array of size n - GeeksforGeeks
Given an array of size n, generate and print all possible combinations of r elements in array. For example, if input array is {1, 2, 3, 4} and r is 2, then output should be {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4} and {3, 4}.
// array contains duplicate or not.
Method 1 (Fix Elements and Recur)

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, data, 0, n-1, 0, r);

}

/* arr[]  ---> Input Array

   data[] ---> Temporary array to store current combination

   start & end ---> Staring and Ending indexes in arr[]

   index  ---> Current index in data[]

   r ---> Size of a combination to be printed */

void combinationUtil(int arr[], int data[], int start, int end, int index, int r)

{

    // Current combination is ready to be printed, print it

    if (index == r)

    {

        for (int j=0; j<r; j++)

            printf("%d ", data[j]);

        printf("\n");

        return;

    }

    // replace index with all possible elements. The condition

    // "end-i+1 >= r-index" makes sure that including one element

    // at index will make a combination with remaining elements

    // at remaining positions ==>

    for (int i=start; i<=end && end-i+1 >= r-index; i++)

    {

        data[index] = arr[i];

        combinationUtil(arr, data, i+1, end, index+1, r);

    }

}

Handle Duplicates
http://ideone.com/ywsqBz

1. void printCombination(int arr[], int n, int r)
2. {
3. // A temporary array to store all combination one by one
4. int data[r];
5. // Sort array to handle duplicates
6. qsort (arr, n, sizeof(int), compare);
7. // Print all combination using temprary array 'data[]'
8. combinationUtil(arr, data, 0, n-1, 0, r);
9. }
10.  
11. /* arr[] ---> Input Array
12.   data[] ---> Temporary array to store current combination
13.   start & end ---> Staring and Ending indexes in arr[]
14.   index ---> Current index in data[]
15.   r ---> Size of a combination to be printed */
16. void combinationUtil(int arr[], int data[], int start, int end, int index, int r)
17. {
18. // Current combination is ready to be printed, print it
19. if (index == r)
20. {
21. for (int i=0; i<r; i++)
22. printf("%d " ,data[i]);
23. printf("\n");
24. return;
25. }
26.  
27. // replace index with all possible elements. The condition
28. // "end-i+1 >= r-index" makes sure that including one element
29. // at index will make a combination with remaining elements
30. // at remaining positions
31. for (int i=start; i<=end && end-i+1 >= r-index; i++)
32. {
33. data[index] = arr[i];
34. combinationUtil(arr, data, i+1, end, index+1, r);
35.  
36.  
37. // Remove duplicates
38. while (arr[i] == arr[i+1])
39. i++;
40. }
41. }

Method 2 (Include and Exclude every element)
This is much easier to code.

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);

}

Read full article from Print all possible combinations of r elements in a given array of size n - GeeksforGeeks