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

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

Example

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.