All combinations of size r from an array
Last Updated :
20 May, 2025
You are given an array arr[] consisting of n elements. Your task is to generate and print all possible combinations of exactly r elements from this array.
Note: A combination is a selection of items where the order does not matter. Ensure that each unique group of r elements is printed only once, regardless of order.
Example:
Input: arr = [1, 2, 3, 4], r = 2
Output: 1 2
1 3
1 4
2 3
2 4
3 4
Explanation: We need to generate all possible combinations of size 2 from an array of size 4. The total number of such combinations is given by the formula:
4C2 = 4! / [(4 - 2)! × 2!] = 6 combinations.
Input: arr = [1, 2, 3, 4], r = 3
Output: 1 2 3
1 2 4
1 3 4
2 3 4
Explanation: We need to generate all possible combinations of size 3 from an array of size 4. The total number of such combinations is given by the formula:
4C3 = 4! / [(4 - 3)! × 3!] = 4 combinations.
Using Recursion and Fixing The Elements - O(nCr * r) Time and O(r) Space
The idea is to fix one element at a time at the current index and recursively fill the remaining positions. Starting from the first index, we try all possible elements that can be placed at that position such that the remaining elements can still fill the combination of size r. Once the size of the current combination becomes equal to r, we store or print that combination. To avoid duplicates, we only consider elements for the remaining positions that are on the right side of the current element.
Follow the below given step-by-step approach:
- Start with the first index (initially 0) and fix one element at this index.
- Recursively try to fix the next element at the next index.
- Continue this process until the size of the current combination becomes equal to
r. - At each recursive call, iterate from the current
start index to the end of the array while ensuring there are enough remaining elements to fill the combination. - When the current combination size becomes
r, add it to the result list. - Use a temporary array to build each combination step by step.
- Store the final combinations in a result list and return it.
Following diagram shows recursion tree:
C++
#include <bits/stdc++.h>
using namespace std;
// Helper function to find all combinations
// of size r in an array of size n
void combinationUtil(int ind, int r, vector<int> &data,
vector<vector<int>> &result, vector<int> &arr) {
int n = arr.size();
// If size of current combination is r
if (data.size() == r) {
result.push_back(data);
return;
}
// Replace index with all possible elements
for(int i = ind; i < n; i++) {
// Current element is included
data.push_back(arr[i]);
// Recur for next elements
combinationUtil(i + 1, r, data, result, arr);
// Backtrack to find other combinations
data.pop_back();
}
}
// Function to find all combinations of size r
// in an array of size n
vector<vector<int>> findCombination(vector<int> &arr, int r) {
int n = arr.size();
// to store the result
vector<vector<int>> result;
// Temporary array to store current combination
vector<int> data;
combinationUtil(0, r, data, result, arr);
return result;
}
int main() {
vector<int> arr = {1, 2, 3, 4};
int r = 2;
vector<vector<int>> res = findCombination(arr, r);
for (const auto &comb : res) {
for (int num : comb) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
import java.util.*;
class GfG {
// Helper function to find all combinations
// of size r in an array of size n
static void combinationUtil(int ind, int r, List<Integer> data,
List<List<Integer>> result, int[] arr) {
int n = arr.length;
// If size of current combination is r
if (data.size() == r) {
result.add(new ArrayList<>(data));
return;
}
// Replace index with all possible elements
for (int i = ind; i < n; i++) {
// Current element is included
data.add(arr[i]);
// Recur for next elements
combinationUtil(i + 1, r, data, result, arr);
// Backtrack to find other combinations
data.remove(data.size() - 1);
}
}
// Function to find all combinations of size r
// in an array of size n
static List<List<Integer>> findCombination(int[] arr, int r) {
int n = arr.length;
// to store the result
List<List<Integer>> result = new ArrayList<>();
// Temporary array to store current combination
List<Integer> data = new ArrayList<>();
combinationUtil(0, r, data, result, arr);
return result;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4};
int r = 2;
List<List<Integer>> res = findCombination(arr, r);
for (List<Integer> comb : res) {
for (int num : comb) {
System.out.print(num + " ");
}
System.out.println();
}
}
}
# Helper function to find all combinations
# of size r in an array of size n
def combinationUtil(ind, r, data, result, arr):
n = len(arr)
# If size of current combination is r
if len(data) == r:
result.append(data.copy())
return
# Replace index with all possible elements
for i in range(ind, n):
# Current element is included
data.append(arr[i])
# Recur for next elements
combinationUtil(i + 1, r, data, result, arr)
# Backtrack to find other combinations
data.pop()
# Function to find all combinations of size r
# in an array of size n
def findCombination(arr, r):
n = len(arr)
# to store the result
result = []
# Temporary array to store current combination
data = []
combinationUtil(0, r, data, result, arr)
return result
arr = [1, 2, 3, 4]
r = 2
res = findCombination(arr, r)
for comb in res:
for num in comb:
print(num, end=" ")
print()
using System;
using System.Collections.Generic;
class GfG {
// Helper function to find all combinations
// of size r in an array of size n
static void combinationUtil(int ind, int r, List<int> data,
List<List<int>> result, int[] arr) {
int n = arr.Length;
// If size of current combination is r
if (data.Count == r) {
result.Add(new List<int>(data));
return;
}
// Replace index with all possible elements
for (int i = ind; i < n; i++) {
// Current element is included
data.Add(arr[i]);
// Recur for next elements
combinationUtil(i + 1, r, data, result, arr);
// Backtrack to find other combinations
data.RemoveAt(data.Count - 1);
}
}
// Function to find all combinations of size r
// in an array of size n
static List<List<int>> findCombination(int[] arr, int r) {
int n = arr.Length;
// to store the result
List<List<int>> result = new List<List<int>>();
// Temporary array to store current combination
List<int> data = new List<int>();
combinationUtil(0, r, data, result, arr);
return result;
}
static void Main() {
int[] arr = {1, 2, 3, 4};
int r = 2;
List<List<int>> res = findCombination(arr, r);
foreach (var comb in res) {
foreach (int num in comb) {
Console.Write(num + " ");
}
Console.WriteLine();
}
}
}
// Helper function to find all combinations
// of size r in an array of size n
function combinationUtil(ind, r, data, result, arr) {
const n = arr.length;
// If size of current combination is r
if (data.length === r) {
result.push([...data]);
return;
}
// Replace index with all possible elements
for (let i = ind; i < n; i++) {
// Current element is included
data.push(arr[i]);
// Recur for next elements
combinationUtil(i + 1, r, data, result, arr);
// Backtrack to find other combinations
data.pop();
}
}
// Function to find all combinations of size r
// in an array of size n
function findCombination(arr, r) {
const n = arr.length;
// to store the result
const result = [];
// Temporary array to store current combination
const data = [];
combinationUtil(0, r, data, result, arr);
return result;
}
const arr = [1, 2, 3, 4];
const r = 2;
const res = findCombination(arr, r);
for (const comb of res) {
for (const num of comb) {
process.stdout.write(num + " ");
}
console.log();
}
Output1 2
1 3
1 4
2 3
2 4
3 4
Time Complexity: O(r × C(n, r)), generates all combinations of size r from n elements, which is C(n, r) in total.
Each combination takes O(r) time to construct and store, leading to an overall complexity of O(r × C(n, r)).
Auxiliary Space: O(r), recursion depth reaches up to r, so the maximum stack space used is O(r). We are not including the space used for storing the final combinations
Using Recursion and Including - Excluding Each Element - O(2 ^ n) Time and O(r) Space
The idea is to explore each element in the array by making a binary choice—either include it in the current combination or skip it—while keeping track of the elements chosen so far. We recursively advance through the array, adding elements until the temporary combination reaches size r (at which point it’s recorded), then backtrack to explore all other possibilities. This guarantees that every valid combination of size r is generated.
Follow the below given step-by-step approach:
- Initialize an empty list
data to hold the current combination. - Define a recursive function with parameters
(ind, r, data, result, arr). - If
data.size() == r, add a copy of data to result and return. - If
ind >= arr.size(), return (no more elements to process). - Add
arr[ind] to data. - Recurse with
ind + 1 to include the current element. - Remove the last element from
data (backtrack). - Recurse with
ind + 1 to explore combinations that exclude the current element.
Below is given the implementation:
C++
#include <bits/stdc++.h>
using namespace std;
// Helper function to find all combinations
// of size r in an array of size n
void combinationUtil(int ind, int r, vector<int> &data,
vector<vector<int>> &result, vector<int> &arr) {
int n = arr.size();
// If size of current combination is r
if (data.size() == r) {
result.push_back(data);
return;
}
// If no more elements are left to put in data
if (ind >= n) {
return;
}
// include the current element
data.push_back(arr[ind]);
// Recur for next elements
combinationUtil(ind + 1, r, data, result, arr);
// Backtrack to find other combinations
data.pop_back();
// exclude the current element and move to the next
combinationUtil(ind + 1, r, data, result, arr);
}
// Function to find all combinations of size r
// in an array of size n
vector<vector<int>> findCombination(vector<int> &arr, int r) {
int n = arr.size();
// to store the result
vector<vector<int>> result;
// Temporary array to store current combination
vector<int> data;
combinationUtil(0, r, data, result, arr);
return result;
}
int main() {
vector<int> arr = {1, 2, 3, 4};
int r = 2;
vector<vector<int>> res = findCombination(arr, r);
for (const auto &comb : res) {
for (int num : comb) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
import java.util.*;
class GfG {
// Helper function to find all combinations
// of size r in an array of size n
static void combinationUtil(int ind, int r, List<Integer> data,
List<List<Integer>> result, int[] arr) {
int n = arr.length;
// If size of current combination is r
if (data.size() == r) {
result.add(new ArrayList<>(data));
return;
}
// If no more elements are left to put in data
if (ind >= n) {
return;
}
// include the current element
data.add(arr[ind]);
// Recur for next elements
combinationUtil(ind + 1, r, data, result, arr);
// Backtrack to find other combinations
data.remove(data.size() - 1);
// exclude the current element and move to the next
combinationUtil(ind + 1, r, data, result, arr);
}
// Function to find all combinations of size r
// in an array of size n
static List<List<Integer>> findCombination(int[] arr, int r) {
int n = arr.length;
// to store the result
List<List<Integer>> result = new ArrayList<>();
// Temporary array to store current combination
List<Integer> data = new ArrayList<>();
combinationUtil(0, r, data, result, arr);
return result;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4};
int r = 2;
List<List<Integer>> res = findCombination(arr, r);
for (List<Integer> comb : res) {
for (int num : comb) {
System.out.print(num + " ");
}
System.out.println();
}
}
}
# Helper function to find all combinations
# of size r in an array of size n
def combinationUtil(ind, r, data,
result, arr):
n = len(arr)
# If size of current combination is r
if len(data) == r:
result.append(data.copy())
return
# If no more elements are left to put in data
if ind >= n:
return
# include the current element
data.append(arr[ind])
# Recur for next elements
combinationUtil(ind + 1, r, data, result, arr)
# Backtrack to find other combinations
data.pop()
# exclude the current element and move to the next
combinationUtil(ind + 1, r, data, result, arr)
# Function to find all combinations of size r
# in an array of size n
def findCombination(arr, r):
n = len(arr)
# to store the result
result = []
# Temporary array to store current combination
data = []
combinationUtil(0, r, data, result, arr)
return result
arr = [1, 2, 3, 4]
r = 2
res = findCombination(arr, r)
for comb in res:
for num in comb:
print(num, end=" ")
print()
using System;
using System.Collections.Generic;
class GfG {
// Helper function to find all combinations
// of size r in an array of size n
static void combinationUtil(int ind, int r, List<int> data,
List<List<int>> result, int[] arr) {
int n = arr.Length;
// If size of current combination is r
if (data.Count == r) {
result.Add(new List<int>(data));
return;
}
// If no more elements are left to put in data
if (ind >= n) {
return;
}
// include the current element
data.Add(arr[ind]);
// Recur for next elements
combinationUtil(ind + 1, r, data, result, arr);
// Backtrack to find other combinations
data.RemoveAt(data.Count - 1);
// exclude the current element and move to the next
combinationUtil(ind + 1, r, data, result, arr);
}
// Function to find all combinations of size r
// in an array of size n
static List<List<int>> findCombination(int[] arr, int r) {
int n = arr.Length;
// to store the result
List<List<int>> result = new List<List<int>>();
// Temporary array to store current combination
List<int> data = new List<int>();
combinationUtil(0, r, data, result, arr);
return result;
}
static void Main() {
int[] arr = {1, 2, 3, 4};
int r = 2;
List<List<int>> res = findCombination(arr, r);
foreach (var comb in res) {
foreach (int num in comb) {
Console.Write(num + " ");
}
Console.WriteLine();
}
}
}
// Helper function to find all combinations
// of size r in an array of size n
function combinationUtil(ind, r, data, result, arr) {
const n = arr.length;
// If size of current combination is r
if (data.length === r) {
result.push([...data]);
return;
}
// If no more elements are left to put in data
if (ind >= n) {
return;
}
// include the current element
data.push(arr[ind]);
// Recur for next elements
combinationUtil(ind + 1, r, data, result, arr);
// Backtrack to find other combinations
data.pop();
// exclude the current element and move to the next
combinationUtil(ind + 1, r, data, result, arr);
}
// Function to find all combinations of size r
// in an array of size n
function findCombination(arr, r) {
const n = arr.length;
// to store the result
const result = [];
// Temporary array to store current combination
const data = [];
combinationUtil(0, r, data, result, arr);
return result;
}
const arr = [1, 2, 3, 4];
const r = 2;
const res = findCombination(arr, r);
for (const comb of res) {
for (const num of comb) {
process.stdout.write(num + " ");
}
console.log();
}
Output1 2
1 3
1 4
2 3
2 4
3 4
Using Sort to Handle The Duplicate Elements in Input - O(2 ^ n) Time and O(n) Space
The idea is to eliminate duplicate combinations by first sorting the input array so that identical elements are adjacent, and then, during the recursive generation, skipping any element that is the same as its immediate predecessor at the same recursion depth. This ensures that each unique value is only considered once per position in the combination, preventing repeated outputs.
Follow the below given step-by-step approach:
- Sort the input array before invoking the recursive routine.
- In the recursive helper, iterate
i from ind to n–1. - If
i > ind and arr[i] == arr[i–1], skip this iteration to avoid duplicates. - Include
arr[i] in the current combination list and recurse with ind = i + 1. - Backtrack by removing the last element after the recursive call.
- Continue recursion to consider combinations that exclude
arr[i]. - Whenever the current combination’s size reaches
r, add it to the result.
Below is given the implementation:
C++
#include <bits/stdc++.h>
using namespace std;
// Helper function to find all combinations
// of size r in an array of size n
void combinationUtil(int ind, int r, vector<int> &data,
vector<vector<int>> &result, vector<int> &arr) {
int n = arr.size();
// If size of current combination is r
if (data.size() == r) {
result.push_back(data);
return;
}
// If no more elements are left to put in data
if (ind >= n) {
return;
}
// include the current element
data.push_back(arr[ind]);
// Recur for next elements
combinationUtil(ind + 1, r, data, result, arr);
// Backtrack to find other combinations
data.pop_back();
// exclude the current element and
// move to the next unique element
while(ind + 1 < n && arr[ind] == arr[ind + 1]) {
ind++;
}
combinationUtil(ind + 1, r, data, result, arr);
}
// Function to find all combinations of size r
// in an array of size n
vector<vector<int>> findCombination(vector<int> &arr, int r) {
int n = arr.size();
// to store the result
vector<vector<int>> result;
// sort the array
sort(arr.begin(), arr.end());
// Temporary array to store current combination
vector<int> data;
combinationUtil(0, r, data, result, arr);
return result;
}
int main() {
vector<int> arr = {1, 1, 2, 3, 4};
int r = 2;
vector<vector<int>> res = findCombination(arr, r);
for (const auto &comb : res) {
for (int num : comb) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
import java.util.*;
class GfG {
// Helper function to find all combinations
// of size r in an array of size n
static void combinationUtil(int ind, int r, List<Integer> data,
List<List<Integer>> result, int[] arr) {
int n = arr.length;
// If size of current combination is r
if (data.size() == r) {
result.add(new ArrayList<>(data));
return;
}
// If no more elements are left to put in data
if (ind >= n) {
return;
}
// include the current element
data.add(arr[ind]);
// Recur for next elements
combinationUtil(ind + 1, r, data, result, arr);
// Backtrack to find other combinations
data.remove(data.size() - 1);
// exclude the current element and
// move to the next unique element
while (ind + 1 < n && arr[ind] == arr[ind + 1]) {
ind++;
}
combinationUtil(ind + 1, r, data, result, arr);
}
// Function to find all combinations of size r
// in an array of size n
static List<List<Integer>> findCombination(int[] arr, int r) {
int n = arr.length;
// to store the result
List<List<Integer>> result = new ArrayList<>();
// sort the array
Arrays.sort(arr);
// Temporary array to store current combination
List<Integer> data = new ArrayList<>();
combinationUtil(0, r, data, result, arr);
return result;
}
public static void main(String[] args) {
int[] arr = {1, 1, 2, 3, 4};
int r = 2;
List<List<Integer>> res = findCombination(arr, r);
for (List<Integer> comb : res) {
for (int num : comb) {
System.out.print(num + " ");
}
System.out.println();
}
}
}
# Helper function to find all combinations
# of size r in an array of size n
def combinationUtil(ind, r, data,
result, arr):
n = len(arr)
# If size of current combination is r
if len(data) == r:
result.append(data.copy())
return
# If no more elements are left to put in data
if ind >= n:
return
# include the current element
data.append(arr[ind])
# Recur for next elements
combinationUtil(ind + 1, r, data, result, arr)
# Backtrack to find other combinations
data.pop()
# exclude the current element and
# move to the next unique element
while ind + 1 < n and arr[ind] == arr[ind + 1]:
ind += 1
combinationUtil(ind + 1, r, data, result, arr)
# Function to find all combinations of size r
# in an array of size n
def findCombination(arr, r):
n = len(arr)
# to store the result
result = []
# sort the array
arr.sort()
# Temporary array to store current combination
data = []
combinationUtil(0, r, data, result, arr)
return result
arr = [1, 1, 2, 3, 4]
r = 2
res = findCombination(arr, r)
for comb in res:
for num in comb:
print(num, end=" ")
print()
using System;
using System.Collections.Generic;
class GfG {
// Helper function to find all combinations
// of size r in an array of size n
static void combinationUtil(int ind, int r, List<int> data,
List<List<int>> result, int[] arr) {
int n = arr.Length;
// If size of current combination is r
if (data.Count == r) {
result.Add(new List<int>(data));
return;
}
// If no more elements are left to put in data
if (ind >= n) {
return;
}
// include the current element
data.Add(arr[ind]);
// Recur for next elements
combinationUtil(ind + 1, r, data, result, arr);
// Backtrack to find other combinations
data.RemoveAt(data.Count - 1);
// exclude the current element and
// move to the next unique element
while (ind + 1 < n && arr[ind] == arr[ind + 1]) {
ind++;
}
combinationUtil(ind + 1, r, data, result, arr);
}
// Function to find all combinations of size r
// in an array of size n
static List<List<int>> findCombination(int[] arr, int r) {
int n = arr.Length;
// to store the result
List<List<int>> result = new List<List<int>>();
// sort the array
Array.Sort(arr);
// Temporary array to store current combination
List<int> data = new List<int>();
combinationUtil(0, r, data, result, arr);
return result;
}
static void Main() {
int[] arr = {1, 1, 2, 3, 4};
int r = 2;
List<List<int>> res = findCombination(arr, r);
foreach (var comb in res) {
foreach (int num in comb) {
Console.Write(num + " ");
}
Console.WriteLine();
}
}
}
// Helper function to find all combinations
// of size r in an array of size n
function combinationUtil(ind, r, data, result, arr) {
const n = arr.length;
// If size of current combination is r
if (data.length === r) {
result.push([...data]);
return;
}
// If no more elements are left to put in data
if (ind >= n) {
return;
}
// include the current element
data.push(arr[ind]);
// Recur for next elements
combinationUtil(ind + 1, r, data, result, arr);
// Backtrack to find other combinations
data.pop();
// exclude the current element and
// move to the next unique element
while (ind + 1 < n && arr[ind] === arr[ind + 1]) {
ind++;
}
combinationUtil(ind + 1, r, data, result, arr);
}
// Function to find all combinations of size r
// in an array of size n
function findCombination(arr, r) {
const n = arr.length;
// to store the result
const result = [];
// sort the array
arr.sort((a, b) => a - b);
// Temporary array to store current combination
const data = [];
combinationUtil(0, r, data, result, arr);
return result;
}
const arr = [1, 1, 2, 3, 4];
const r = 2;
const res = findCombination(arr, r);
for (const comb of res) {
for (const num of comb) {
process.stdout.write(num + " ");
}
console.log();
}
Output1 1
1 2
1 3
1 4
2 3
2 4
3 4
Similar Reads
Find bitwise OR of all possible sub-arrays
Given an array A of size N where, 1\leq N \leq 10^{5} . The task is to find the OR of all possible sub-arrays of A and then the OR of all these results. Examples: Input : 1 4 6 Output : 7 All possible subarrays are {1}, {1, 4}, {4, 6} and {1, 4, 6} ORs of these subarrays are 1, 5, 6 and 7. OR of the
9 min read
Find bitwise AND (&) of all possible sub-arrays
Given an array A of size N where 1\leq N \leq 10^{5} . The task is to find the AND of all possible sub-arrays of A and then the AND of all these results. Examples: Input : 1 2 3 Output : 0 All possible subarrays are {1}, {2}, {3}, {1, 2}, {2, 3} and {1, 2, 3} ANDs of these subarrays are 1, 2, 3, 0,
7 min read
Combinations from n arrays picking one element from each array
Given a list of arrays, find all combinations where each combination contains one element from each given array. Examples: Input : [ [1, 2], [3, 4] ] Output : 1 3 1 4 2 3 2 4 Input : [ [1], [2, 3, 4], [5] ] Output : 1 2 5 1 3 5 1 4 5 We keep an array of size equal to the total no of arrays. This arr
8 min read
Make alphabets using the elements of an array
Given an array of positive integers, find all the alphabets that we can make using elements of the array. Examples : Input : arr[] = {6, 5} Output : A In this example, we can take 6 and 5 as 65 that gives us A. Input : arr[] = {5, 6, 6} Output : A B Here we can take 6 and 5 as 65 to make A. And 6 an
9 min read
Find elements of original array from doubled array
Given an array arr[] of 2*N integers such that it consists of all elements along with the twice values of another array, say A[], the task is to find the array A[]. Examples: Input: arr[] = {4, 1, 18, 2, 9, 8}Output: 1 4 9Explanation:After taking double values of 1, 4, and 9 then adding them to the
7 min read
Product of all Subarrays of an Array
Given an array of integers arr of size N, the task is to print products of all subarrays of the array. Examples: Input: arr[] = {2, 4} Output: 64 Here, subarrays are [2], [2, 4], [4] Products are 2, 8, 4 Product of all Subarrays = 64 Input : arr[] = {10, 3, 7} Output : 27783000 Here, subarrays are [
7 min read
Product of all non repeating Subarrays of an Array
Given an array containing distinct integers arr[] of size N, the task is to print the product of all non-repeating subarrays of the array. Examples: Input: arr[] = {2, 4} Output: 64 Explanation: The possible subarrays for the given array are {2}, {2, 4}, {4} The products are 2, 8, 4 respectively. Th
5 min read
Product of all Subarrays of an Array | Set 2
Given an array arr[] of integers of size N, the task is to find the products of all subarrays of the array.Examples: Input: arr[] = {2, 4} Output: 64 Explanation: Here, subarrays are {2}, {2, 4}, and {4}. Products of each subarray are 2, 8, 4. Product of all Subarrays = 64Input: arr[] = {1, 2, 3} Ou
5 min read
Generate an array of size N according to the given rules
Given a number N, the task is to create an array arr[] of size N, where the value of the element at every index i is filled according to the following rules: arr[i] = ((i - 1) - k), where k is the index of arr[i - 1] that has appeared second most recently. This rule is applied when arr[i - 1] is pre
10 min read
Convert an Array to reduced form using Vector of pairs
Given an array with n distinct elements, convert the given array to a form where all elements are in range from 0 to n-1. The order of elements is same, i.e., 0 is placed in place of smallest element, 1 is placed for second smallest element, ... n-1 is placed for largest element. Input: arr[] = {10,
11 min read