# Print all Possible Combinations of R Elements in a given Array of size N

Difficulty Level Medium
Frequently asked in GreyOrange Oxigen Wallet
MathViews 1348

## Problem Statement

In the “Print all Possible Combinations of R Elements in a given Array of size N” problem, we have given an array of size n. Find all combinations of size r in the array.

## Input Format

Th first and only one line containing an integer N.

Second-line containing n space-separated integers.

The third line containing an integer R.

## Output Format

Print all Possible Combinations of R Elements of a given array such that every line containing exactly one combination.

## Constraints

• 1<=N<=10
• 1<=a[i]<=10^9

```4
1 2 3 4
2```
```1 2
1 3
1 4
2 3
2 4
3 4```

## Algorithm

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

We create a temporary array ‘data[]’ which stores all output one by one. The idea is to start from the first index (index = 0) in data[], one by one fix elements at this index and recur for the remaining indexes. Let the input array be {1, 2, 3, 4, 5} and r be 3. We first fix 1 at index 0 in data[], then recur for remaining indexes, then we fix 2 at index 0 and recur. Finally, we fix 3 and recur for the remaining indexes. When the number of elements in data[] becomes equal to r (size of a combination), we print data[].

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

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

## Implementation

### C++ Program to Print all Possible Combinations of R Elements in a given Array of size N

```#include<bits/stdc++.h>
using namespace std;

void combination(int arr[], int data[], int start, int end, int index, int r)
{
if(index == r)
{
for (int j = 0; j < r; j++)
cout << data[j] << " ";
cout << endl;
return;
}
for(int i = start; i <= end && end - i + 1 >= r - index; i++)
{
data[index] = arr[i];
combination(arr, data, i+1, end, index+1, r);
}
}

int main()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int r;
cin>>r;
int data[r];
combination(a,data,0,n-1,0,r);
}
```

### Java Program to Print all Possible Combinations of R Elements in a given Array of size N

```import java.util.ArrayList;
import java.util.Scanner;
class sum
{
public static void combination(int arr[], int data[], int start, int end, int index, int r)
{
if(index == r)
{
for(int j = 0; j < r; j++)
System.out.print(data[j]+" ");
System.out.println();
return;
}
for(int i = start; i <= end && end - i + 1 >= r - index; i++)
{
data[index] = arr[i];
combination(arr, data, i+1, end, index+1, r);
}
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int a[] = new int [n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
int r = sr.nextInt();
int data [] = new int[r];
combination(a,data,0,n-1,0,r);
}
}
```
```5
105 21 35 10 183
3```
```105 21 35
105 21 10
105 21 183
105 35 10
105 35 183
105 10 183
21 35 10
21 35 183
21 10 183
35 10 183```

## Complexity Analysis

### Time Complexity

O(nCr) where n is the size of the given array and r is the number of elements which we take for combination.

### Space Complexity

O(1) because we don’t use any auxiliary space at here.

Translate »