Posted on by Kalkicode
Code Backtracking

# 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

1. `combinations(arr, result, n, k, i, j)`: This function generates and prints all possible combinations of size `k` 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 the `result` array.
2. If `j` reaches the desired size `k`, it means a valid combination has been formed, so the function prints the current combination.

3. If `i` is greater than or equal to `n`, it stops the recursion process.

4. The function iterates through the array from index `i` to `n - 1`. It puts the current element into the `result` array at index `j` and then recursively calls the function with the next element.

5. `printCombinations(arr, n, k)`: This function initializes the `result` array and calls the `combinations` 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)
{
char[] arr = {
'A' , 'B' , 'C' , 'D' , 'E'
};
// Get the length of array elements
int n = arr.length;
// Here k = 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()
{
char arr[] = {
'A' , 'B' , 'C' , 'D' , 'E'
};
// Get the length of array elements
int n = sizeof(arr) / sizeof(arr[0]);
// Here k = 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)
{
char[] arr = {
'A' , 'B' , 'C' , 'D' , 'E'
};
// Get the length of array elements
int n = arr.Length;
// Here k = 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()
{
\$arr = array('A', 'B', 'C', 'D', 'E');
// Get the length of array elements
\$n = count(\$arr);
// Here k = 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 arr = ['A', 'B', 'C', 'D', 'E'];
// Get the length of array elements
var n = arr.length;
// Here k = 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() :
arr = ['A', 'B', 'C', 'D', 'E']
n = len(arr)
#  Here k = 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()
arr = ['A', 'B', 'C', 'D', 'E']
#  Get the length of array elements
n = arr.length
#  Here k = 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
}
}``````

#### 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 arr: [Character] = ["A", "B", "C", "D", "E"];
// Get the length of array elements
let n: Int = arr.count;
// Here k = 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 arr: Array < Char > = arrayOf('A', 'B', 'C', 'D', 'E');
// Get the length of array elements
val n: Int = arr.count();
// Here k = 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)!)`.

## Comment

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.

Categories
Relative Post