Print k size combinations in given array
The problem involves generating all possible combinations of length
k
from a given array of elements. Each combination is a selection of k
elements from the
array without considering the order. This problem can be solved using a recursive approach to explore all possible
combinations.
Problem Statement
Given an array of elements and an integer k
, the task is to generate and print all possible
combinations of length k
from the array.
Example
For the input array ['A', 'B', 'C', 'D', 'E']
and k = 3
, the possible combinations are:
- ['A', 'B', 'C']
- ['A', 'B', 'D']
- ['A', 'B', 'E']
- ['A', 'C', 'D']
- ['A', 'C', 'E']
- ['A', 'D', 'E']
- ['B', 'C', 'D']
- ['B', 'C', 'E']
- ['B', 'D', 'E']
- ['C', 'D', 'E']
Idea to Solve
To solve this problem, you can use a recursive approach where you iterate through the array elements, select an element, and then recursively find the combinations for the remaining elements. You keep track of the current combination size and the index from where to start considering elements.
Pseudocode
function combinations(arr, result, n, k, i, j):
if j == k:
for count = 0 to k - 1:
print result[count]
print "\n"
return
else if i >= n:
return
for count = i to n - 1:
result[j] = arr[count]
combinations(arr, result, n, k, count + 1, j + 1)
function printCombinations(arr, n, k):
if k <= 0 or k > n or n <= 0:
return
result[k]
combinations(arr, result, n, k, 0, 0)
function main():
arr = ['A', 'B', 'C', 'D', 'E']
n = length of arr
k = 3
printCombinations(arr, n, k)
main()
Algorithm Explanation
-
combinations(arr, result, n, k, i, j)
: This function generates and prints all possible combinations of sizek
from the given array. It takes six parameters:arr
: The array of elements.result
: An array to store the current combination being formed.n
: The number of elements in the array.k
: The desired size of combinations.i
: The current index in the array.j
: The current index in theresult
array.
-
If
j
reaches the desired sizek
, it means a valid combination has been formed, so the function prints the current combination. -
If
i
is greater than or equal ton
, it stops the recursion process. -
The function iterates through the array from index
i
ton - 1
. It puts the current element into theresult
array at indexj
and then recursively calls the function with the next element. -
printCombinations(arr, n, k)
: This function initializes theresult
array and calls thecombinations
function to generate and print combinations.
Code Solution
// C program for
// Print k size combinations in given array
#include <stdio.h>
// Recursively, printing the combination of given size
void combinations(char arr[], char result[], int n, int k, int i, int j)
{
if (j == k)
{
// When k combination are found
// Print calculated combination
for (int count = 0; count < k; ++count)
{
printf(" %c", result[count]);
}
printf("\n");
return;
}
else if (i >= n)
{
// Stop recursion process when (i) is greater than or equal to given size
return;
}
for (int count = i; count < n; ++count)
{
// Put new element
result[j] = arr[count];
// Recursively finding the solution
combinations(arr, result, n, k, count + 1, j + 1);
}
}
// Handles the request to print combinations of given array
void printCombinations(char arr[], int n, int k)
{
if (k <= 0 || k > n || n <= 0)
{
return;
}
// auxiliary space to store result
char result[k];
// Find combinations from left to right
combinations(arr, result, n, k, 0, 0);
}
int main(int argc, char const *argv[])
{
char arr[] = {
'A' , 'B' , 'C' , 'D' , 'E'
};
// Get the length of array elements
int n = sizeof(arr) / sizeof(arr[0]);
// Here k = 3
printCombinations(arr, n, 3);
return 0;
}
input
A B C
A B D
A B E
A C D
A C E
A D E
B C D
B C E
B D E
C D E
/*
Java Program for
Print k size combinations in given array
*/
public class Combinations
{
// Recursively, printing the combination of given size
public void findCombinations(char[] arr, char[] result, int n, int k, int i, int j)
{
if (j == k)
{
// When k combination are found
// Print calculated combination
for (int count = 0; count < k; ++count)
{
System.out.print(" " + result[count]);
}
System.out.print("\n");
return;
}
else if (i >= n)
{
// Stop recursion process when (i) is greater than or equal to given size
return;
}
for (int count = i; count < n; ++count)
{
// Put new element
result[j] = arr[count];
// Recursively finding the solution
findCombinations(arr, result, n, k, count + 1, j + 1);
}
}
// Handles the request to print combinations of given array
public void printCombinations(char[] arr, int n, int k)
{
if (k <= 0 || k > n || n <= 0)
{
return;
}
// auxiliary space to store result
char[] result = new char[k];
// Find combinations from left to right
findCombinations(arr, result, n, k, 0, 0);
}
public static void main(String[] args)
{
Combinations task = new Combinations();
char[] arr = {
'A' , 'B' , 'C' , 'D' , 'E'
};
// Get the length of array elements
int n = arr.length;
// Here k = 3
task.printCombinations(arr, n, 3);
}
}
input
A B C
A B D
A B E
A C D
A C E
A D E
B C D
B C E
B D E
C D E
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Print k size combinations in given array
*/
class Combinations
{
public:
// Recursively, printing the combination of given size
void findCombinations(char arr[], char result[], int n, int k, int i, int j)
{
if (j == k)
{
// When k combination are found
// Print calculated combination
for (int count = 0; count < k; ++count)
{
cout << " " << result[count];
}
cout << "\n";
return;
}
else
{
if (i >= n)
{
// Stop recursion process when (i) is greater than or equal to given size
return;
}
}
for (int count = i; count < n; ++count)
{
// Put new element
result[j] = arr[count];
// Recursively finding the solution
this->findCombinations(arr, result, n, k, count + 1, j + 1);
}
}
// Handles the request to print combinations of given array
void printCombinations(char arr[], int n, int k)
{
if (k <= 0 || k > n || n <= 0)
{
return;
}
// auxiliary space to store result
char result[k];
// Find combinations from left to right
this->findCombinations(arr, result, n, k, 0, 0);
}
};
int main()
{
Combinations *task = new Combinations();
char arr[] = {
'A' , 'B' , 'C' , 'D' , 'E'
};
// Get the length of array elements
int n = sizeof(arr) / sizeof(arr[0]);
// Here k = 3
task->printCombinations(arr, n, 3);
return 0;
}
input
A B C
A B D
A B E
A C D
A C E
A D E
B C D
B C E
B D E
C D E
// Include namespace system
using System;
/*
Csharp Program for
Print k size combinations in given array
*/
public class Combinations
{
// Recursively, printing the combination of given size
public void findCombinations(char[] arr, char[] result, int n, int k, int i, int j)
{
if (j == k)
{
// When k combination are found
// Print calculated combination
for (int count = 0; count < k; ++count)
{
Console.Write(" " + result[count]);
}
Console.Write("\n");
return;
}
else
{
if (i >= n)
{
// Stop recursion process when (i) is greater than or equal to given size
return;
}
}
for (int count = i; count < n; ++count)
{
// Put new element
result[j] = arr[count];
// Recursively finding the solution
this.findCombinations(arr, result, n, k, count + 1, j + 1);
}
}
// Handles the request to print combinations of given array
public void printCombinations(char[] arr, int n, int k)
{
if (k <= 0 || k > n || n <= 0)
{
return;
}
// auxiliary space to store result
char[] result = new char[k];
// Find combinations from left to right
this.findCombinations(arr, result, n, k, 0, 0);
}
public static void Main(String[] args)
{
Combinations task = new Combinations();
char[] arr = {
'A' , 'B' , 'C' , 'D' , 'E'
};
// Get the length of array elements
int n = arr.Length;
// Here k = 3
task.printCombinations(arr, n, 3);
}
}
input
A B C
A B D
A B E
A C D
A C E
A D E
B C D
B C E
B D E
C D E
<?php
/*
Php Program for
Print k size combinations in given array
*/
class Combinations
{
// Recursively, printing the combination of given size
public function findCombinations($arr, $result, $n, $k, $i, $j)
{
if ($j == $k)
{
// When k combination are found
// Print calculated combination
for ($count = 0; $count < $k; ++$count)
{
echo " ".$result[$count];
}
echo "\n";
return;
}
else
{
if ($i >= $n)
{
// Stop recursion process when (i) is greater than or equal to given size
return;
}
}
for ($count = $i; $count < $n; ++$count)
{
// Put new element
$result[$j] = $arr[$count];
// Recursively finding the solution
$this->findCombinations($arr, $result, $n, $k, $count + 1, $j + 1);
}
}
// Handles the request to print combinations of given array
public function printCombinations($arr, $n, $k)
{
if ($k <= 0 || $k > $n || $n <= 0)
{
return;
}
// auxiliary space to store result
$result = array_fill(0, $k, ' ');
// Find combinations from left to right
$this->findCombinations($arr, $result, $n, $k, 0, 0);
}
}
function main()
{
$task = new Combinations();
$arr = array('A', 'B', 'C', 'D', 'E');
// Get the length of array elements
$n = count($arr);
// Here k = 3
$task->printCombinations($arr, $n, 3);
}
main();
input
A B C
A B D
A B E
A C D
A C E
A D E
B C D
B C E
B D E
C D E
/*
Node JS Program for
Print k size combinations in given array
*/
class Combinations
{
// Recursively, printing the combination of given size
findCombinations(arr, result, n, k, i, j)
{
if (j == k)
{
// When k combination are found
// Print calculated combination
for (var count = 0; count < k; ++count)
{
process.stdout.write(" " + result[count]);
}
process.stdout.write("\n");
return;
}
else
{
if (i >= n)
{
// Stop recursion process when (i) is greater than or equal to given size
return;
}
}
for (var count = i; count < n; ++count)
{
// Put new element
result[j] = arr[count];
// Recursively finding the solution
this.findCombinations(arr, result, n, k, count + 1, j + 1);
}
}
// Handles the request to print combinations of given array
printCombinations(arr, n, k)
{
if (k <= 0 || k > n || n <= 0)
{
return;
}
// auxiliary space to store result
var result = Array(k).fill(' ');
// Find combinations from left to right
this.findCombinations(arr, result, n, k, 0, 0);
}
}
function main()
{
var task = new Combinations();
var arr = ['A', 'B', 'C', 'D', 'E'];
// Get the length of array elements
var n = arr.length;
// Here k = 3
task.printCombinations(arr, n, 3);
}
main();
input
A B C
A B D
A B E
A C D
A C E
A D E
B C D
B C E
B D E
C D E
# Python 3 Program for
# Print k size combinations in given array
class Combinations :
# Recursively, printing the combination of given size
def findCombinations(self, arr, result, n, k, i, j) :
if (j == k) :
# When k combination are found
# Print calculated combination
count = 0
while (count < k) :
print(" ", result[count], end = "")
count += 1
print(end = "\n")
return
else :
if (i >= n) :
# Stop recursion process when (i) is greater than or equal to given size
return
count = i
while (count < n) :
# Put new element
result[j] = arr[count]
# Recursively finding the solution
self.findCombinations(arr, result, n, k, count + 1, j + 1)
count += 1
# Handles the request to print combinations of given list
def printCombinations(self, arr, n, k) :
if (k <= 0 or k > n or n <= 0) :
return
result = [ ' '
] * (k)
# Find combinations from left to right
self.findCombinations(arr, result, n, k, 0, 0)
def main() :
task = Combinations()
arr = ['A', 'B', 'C', 'D', 'E']
n = len(arr)
# Here k = 3
task.printCombinations(arr, n, 3)
if __name__ == "__main__": main()
input
A B C
A B D
A B E
A C D
A C E
A D E
B C D
B C E
B D E
C D E
# Ruby Program for
# Print k size combinations in given array
class Combinations
# Recursively, printing the combination of given size
def findCombinations(arr, result, n, k, i, j)
if (j == k)
# When k combination are found
# Print calculated combination
count = 0
while (count < k)
print(" ", result[count])
count += 1
end
print("\n")
return
else
if (i >= n)
# Stop recursion process when (i) is greater than or equal to given size
return
end
end
count = i
while (count < n)
# Put new element
result[j] = arr[count]
# Recursively finding the solution
self.findCombinations(arr, result, n, k, count + 1, j + 1)
count += 1
end
end
# Handles the request to print combinations of given array
def printCombinations(arr, n, k)
if (k <= 0 || k > n || n <= 0)
return
end
# auxiliary space to store result
result = Array.new(k) { ' '
}
# Find combinations from left to right
self.findCombinations(arr, result, n, k, 0, 0)
end
end
def main()
task = Combinations.new()
arr = ['A', 'B', 'C', 'D', 'E']
# Get the length of array elements
n = arr.length
# Here k = 3
task.printCombinations(arr, n, 3)
end
main()
input
A B C
A B D
A B E
A C D
A C E
A D E
B C D
B C E
B D E
C D E
/*
Scala Program for
Print k size combinations in given array
*/
class Combinations()
{
// Recursively, printing the combination of given size
def findCombinations(arr: Array[Char], result: Array[Char], n: Int, k: Int, i: Int, j: Int): Unit = {
if (j == k)
{
// When k combination are found
// Print calculated combination
var count: Int = 0;
while (count < k)
{
print(" " + result(count));
count += 1;
}
print("\n");
return;
}
else
{
if (i >= n)
{
// Stop recursion process when (i) is greater than or equal to given size
return;
}
}
var count: Int = i;
while (count < n)
{
// Put new element
result(j) = arr(count);
// Recursively finding the solution
findCombinations(arr, result, n, k, count + 1, j + 1);
count += 1;
}
}
// Handles the request to print combinations of given array
def printCombinations(arr: Array[Char], n: Int, k: Int): Unit = {
if (k <= 0 || k > n || n <= 0)
{
return;
}
// auxiliary space to store result
var result: Array[Char] = Array.fill[Char](k)(' ');
// Find combinations from left to right
findCombinations(arr, result, n, k, 0, 0);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Combinations = new Combinations();
var arr: Array[Char] = Array('A', 'B', 'C', 'D', 'E');
// Get the length of array elements
var n: Int = arr.length;
// Here k = 3
task.printCombinations(arr, n, 3);
}
}
input
A B C
A B D
A B E
A C D
A C E
A D E
B C D
B C E
B D E
C D E
/*
Swift 4 Program for
Print k size combinations in given array
*/
class Combinations
{
// Recursively, printing the combination of given size
func findCombinations(_ arr: [Character], _ result: inout[Character], _ n: Int, _ k: Int, _ i: Int, _ j: Int)
{
if (j == k)
{
// When k combination are found
// Print calculated combination
var count: Int = 0;
while (count < k)
{
print(" ", result[count], terminator: "");
count += 1;
}
print(terminator: "\n");
return;
}
else
{
if (i >= n)
{
// Stop recursion process when (i) is greater than or equal to given size
return;
}
}
var count: Int = i;
while (count < n)
{
// Put new element
result[j] = arr[count];
// Recursively finding the solution
self.findCombinations(arr, &result, n, k, count + 1, j + 1);
count += 1;
}
}
// Handles the request to print combinations of given array
func printCombinations(_ arr: [Character], _ n: Int, _ k: Int)
{
if (k <= 0 || k > n || n <= 0)
{
return;
}
// auxiliary space to store result
var result: [Character] = Array(repeating: " ", count: k);
// Find combinations from left to right
self.findCombinations(arr, &result, n, k, 0, 0);
}
}
func main()
{
let task: Combinations = Combinations();
let arr: [Character] = ["A", "B", "C", "D", "E"];
// Get the length of array elements
let n: Int = arr.count;
// Here k = 3
task.printCombinations(arr, n, 3);
}
main();
input
A B C
A B D
A B E
A C D
A C E
A D E
B C D
B C E
B D E
C D E
/*
Kotlin Program for
Print k size combinations in given array
*/
class Combinations
{
// Recursively, printing the combination of given size
fun findCombinations(arr: Array < Char > , result: Array < Char > , n: Int, k: Int, i: Int, j: Int): Unit
{
if (j == k)
{
var count: Int = 0;
while (count < k)
{
print(" " + result[count]);
count += 1;
}
print("\n");
return;
}
else
{
if (i >= n)
{
// Stop recursion process when (i) is greater than or equal to given size
return;
}
}
var count: Int = i;
while (count < n)
{
// Put new element
result[j] = arr[count];
// Recursively finding the solution
this.findCombinations(arr, result, n, k, count + 1, j + 1);
count += 1;
}
}
// Handles the request to print combinations of given array
fun printCombinations(arr: Array < Char > , n: Int, k: Int): Unit
{
if (k <= 0 || k > n || n <= 0)
{
return;
}
// auxiliary space to store result
val result: Array < Char > = Array(k)
{
' '
};
// Find combinations from left to right
this.findCombinations(arr, result, n, k, 0, 0);
}
}
fun main(args: Array < String > ): Unit
{
val task: Combinations = Combinations();
val arr: Array < Char > = arrayOf('A', 'B', 'C', 'D', 'E');
// Get the length of array elements
val n: Int = arr.count();
// Here k = 3
task.printCombinations(arr, n, 3);
}
input
A B C
A B D
A B E
A C D
A C E
A D E
B C D
B C E
B D E
C D E
Time Complexity
The time complexity of the algorithm depends on the number of combinations to be generated. In this case, the number
of combinations is n choose k
, which is proportional to n! / (k! * (n - k)!)
.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment