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
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

// 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;
}

  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);
	}
}

 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;
}

 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);
	}
}

 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();

 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();

 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()

  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()

 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);
	}
}

 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();

  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);
}

 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)!).