Given a set of characters and a positive integer k, print all possible strings of length k that can be formed from the given set.
Examples:
Input:
set[] = {'a', 'b'}, k = 3
Output:
aaa
aab
aba
abb
baa
bab
bba
bbb
Input:
set[] = {'a', 'b', 'c', 'd'}, k = 1
Output:
a
b
c
d
For a given set of size n, there will be n^k possible strings of length k. The idea is to start from an empty output string (we call it prefix in following code). One by one add all characters to prefix. For every character added, print all possible strings with current prefix by recursively calling for k equals to k-1.
Below is the implementation of above idea :
C++
// C++ program to print all // possible strings of length k#include <bits/stdc++.h>using namespace std; // The main recursive method// to print all possible // strings of length kvoid printAllKLengthRec(char set[], string prefix, int n, int k){ // Base case: k is 0, // print prefix if (k == 0) { cout << (prefix) << endl; return; } // One by one add all characters // from set and recursively // call for k equals to k-1 for (int i = 0; i < n; i++) { string newPrefix; // Next character of input added newPrefix = prefix + set[i]; // k is decreased, because // we have added a new character printAllKLengthRec(set, newPrefix, n, k - 1); }}void printAllKLength(char set[], int k,int n){ printAllKLengthRec(set, "", n, k);}// Driver Codeint main(){ cout << "First Test" << endl; char set1[] = {'a', 'b'}; int k = 3; printAllKLength(set1, k, 2); cout << "Second Test\n"; char set2[] = {'a', 'b', 'c', 'd'}; k = 1; printAllKLength(set2, k, 4);}// This code is contributed // by Mohit kumar |
Java
// Java program to print all // possible strings of length kclass GFG { // The method that prints all // possible strings of length k.// It is mainly a wrapper over // recursive function printAllKLengthRec()static void printAllKLength(char[] set, int k){ int n = set.length; printAllKLengthRec(set, "", n, k);}// The main recursive method// to print all possible // strings of length kstatic void printAllKLengthRec(char[] set, String prefix, int n, int k){ // Base case: k is 0, // print prefix if (k == 0) { System.out.println(prefix); return; } // One by one add all characters // from set and recursively // call for k equals to k-1 for (int i = 0; i < n; ++i) { // Next character of input added String newPrefix = prefix + set[i]; // k is decreased, because // we have added a new character printAllKLengthRec(set, newPrefix, n, k - 1); }}// Driver Codepublic static void main(String[] args){ System.out.println("First Test"); char[] set1 = {'a', 'b'}; int k = 3; printAllKLength(set1, k); System.out.println("\nSecond Test"); char[] set2 = {'a', 'b', 'c', 'd'}; k = 1; printAllKLength(set2, k); }} |
Python3
# Python 3 program to print all # possible strings of length k # The method that prints all # possible strings of length k.# It is mainly a wrapper over # recursive function printAllKLengthRec()def printAllKLength(set, k): n = len(set) printAllKLengthRec(set, "", n, k)# The main recursive method# to print all possible # strings of length kdef printAllKLengthRec(set, prefix, n, k): # Base case: k is 0, # print prefix if (k == 0) : print(prefix) return # One by one add all characters # from set and recursively # call for k equals to k-1 for i in range(n): # Next character of input added newPrefix = prefix + set[i] # k is decreased, because # we have added a new character printAllKLengthRec(set, newPrefix, n, k - 1)# Driver Codeif __name__ == "__main__": print("First Test") set1 = ['a', 'b'] k = 3 printAllKLength(set1, k) print("\nSecond Test") set2 = ['a', 'b', 'c', 'd'] k = 1 printAllKLength(set2, k)# This code is contributed # by ChitraNayal |
C#
// C# program to print all // possible strings of length kusing System;class GFG { // The method that prints all // possible strings of length k.// It is mainly a wrapper over // recursive function printAllKLengthRec()static void printAllKLength(char[] set, int k){ int n = set.Length; printAllKLengthRec(set, "", n, k);}// The main recursive method// to print all possible // strings of length kstatic void printAllKLengthRec(char[] set, String prefix, int n, int k){ // Base case: k is 0, // print prefix if (k == 0) { Console.WriteLine(prefix); return; } // One by one add all characters // from set and recursively // call for k equals to k-1 for (int i = 0; i < n; ++i) { // Next character of input added String newPrefix = prefix + set[i]; // k is decreased, because // we have added a new character printAllKLengthRec(set, newPrefix, n, k - 1); }}// Driver Codestatic public void Main (){ Console.WriteLine("First Test"); char[] set1 = {'a', 'b'}; int k = 3; printAllKLength(set1, k); Console.WriteLine("\nSecond Test"); char[] set2 = {'a', 'b', 'c', 'd'}; k = 1; printAllKLength(set2, k); }}// This code is contributed by Ajit. |
Javascript
<script>// Javascript program to print all // possible strings of length k // The method that prints all // possible strings of length k. // It is mainly a wrapper over // recursive function printAllKLengthRec() function printAllKLength(set,k) { let n = set.length; printAllKLengthRec(set, "", n, k); } // The main recursive method // to print all possible // strings of length k function printAllKLengthRec(set,prefix,n,k) { // Base case: k is 0, // print prefix if (k == 0) { document.write(prefix+"<br>"); return; } // One by one add all characters // from set and recursively // call for k equals to k-1 for (let i = 0; i < n; ++i) { // Next character of input added let newPrefix = prefix + set[i]; // k is decreased, because // we have added a new character printAllKLengthRec(set, newPrefix, n, k - 1); } } // Driver Code document.write("First Test<br>"); let set1=['a', 'b']; let k = 3; printAllKLength(set1, k); document.write("<br>Second Test<br>"); let set2 = ['a', 'b', 'c', 'd']; k = 1; printAllKLength(set2, k); // This code is contributed by avanitrachhadiya2155 </script> |
Output:
First Test aaa aab aba abb baa bab bba bbb Second Test a b c d
Time complexity: O(nk)
Auxiliary Space: O(k)
The above solution is mainly a generalization of this post.
This article is contributed by Abhinav Ramana. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
