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

Given an array of size n, find all combinations of size r in the array.

Example

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

OUTPUT:
{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}

Method 1(Recursive):

In this method, the main idea is to create a temporary array sol[] of size r and store result in it.

Algorithm

1. Start from the first index in sol[], one by one fix elements at this index and recur for remaining indexes.

2. If the sol[] array becomes full then print the sol[] array.

C++ Program

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
void allCombinations(int arr[], int sol[], int start, int end, 
                     int index, int r);
 
//This function calls allCombinations, which 
//recursively prints all combinations 
void printCombination(int arr[], int n, int r)
{
    // A temporary array to store all combinations one by one
    int sol[r];
 
    // Print all combination using temprary array 'sol[]'
    allCombinations(arr, sol, 0, n-1, 0, r);
}
 
/* arr[]  ---> Input Array
   sol[] ---> Temporary array to store current combination
   start & end ---> Staring and Ending indexes in arr[]
   index  ---> Current index in sol[]
   r ---> Size of a combination to be printed */
void allCombinations(int arr[], int sol[], 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 ", sol[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++)
    {
        sol[index] = arr[i];
        allCombinations(arr, sol, i+1, end, index+1, r);
    }
}
 
// Driver program to test above functions
int main()
{
    int arr[] = {1, 2, 3, 4};
    int r = 2;
    int n = sizeof(arr)/sizeof(arr[0]);
    printCombination(arr, n, r);
}
Try It

Method 2 (Include and Exclude every element)
Similar to above method, we create a temporary array sol[] of size r and for every element in the input array recur for 2 cases

Algorithm

1. The element is included in current combination ie, we put the data in sol[] and increment the index
2. The element is excluded in current combination ie, we do not put the element and do not change index.

C++ Program

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

 

 

 


Next > < Prev
Scroll to Top