## 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);
}
```

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;
}
```