Posted on by Kalkicode
Code Backtracking

# Print all possible strings of length N in a set

The problem at hand is to generate and print all possible strings of a fixed length N using characters from a given set. In this scenario, we are using the characters 'A' and 'B' as the set. The objective is to generate all combinations of these characters of length N and print them.

## Problem Statement and Description

Given a set of characters (in this case, 'A' and 'B'), the goal is to generate all possible strings of length N using these characters and print them. For instance, if N is 4 and the set contains only 'A' and 'B', the program should generate all 16 combinations of 'A' and 'B' of length 4 and print them.

``````AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB``````

## Example

Let's illustrate this with a smaller example where N = 2 and the set contains only 'A' and 'B'.

• For N = 2, the possible combinations are: "AA", "AB", "BA", "BB".
• So, the program should output:
``````AA
AB
BA
BB``````

## Idea to Solve the Problem

To solve this problem, we can use a recursive approach. We'll iterate through each character in the set and append it to the current output string. Then, we'll recursively call the function with a decremented value of N until N becomes 0. At that point, we'll print the generated string.

## Pseudocode

``````function generateStrings(record, output, n, size):
if n == 0:
print(output)
return
for i in range(size):
generateStrings(record, output + record[i], n - 1, size)

record = ['A', 'B']
size = length of record
n = desired string length
generateStrings(record, "", n, size)``````

## Algorithm Explanation

1. Start by defining a function `generateStrings` that takes parameters: `record` (the character set), `output` (the current generated string), `n` (remaining length to generate), and `size` (size of the character set).

2. In the `generateStrings` function, check if `n` is 0. If so, it means we have generated a string of desired length. In this case, print the `output` string and return.

3. If `n` is not 0, iterate through each character in the `record` set.

4. For each character, recursively call the `generateStrings` function with updated parameters:

• Append the current character to the `output` string.
• Decrement `n` by 1.
• Keep `size` unchanged.
5. When all recursive calls return, the program will have generated and printed all possible strings of length `N` using characters from the given set.

6. In the `main` function, define the character set `record` and get the size of the set (`size`). Also, specify the desired length of the generated strings (`n`).

7. Call the `generateStrings` function with initial `output` as an empty string, the desired `n`, and the size of the character set.

## Code Solution

``````/*
Java program
Print all possible strings of length N in a set
*/
public class Combinations
{
public void result(char[] record, String output, int n, int size)
{
if (n == 0)
{
// Display output
System.out.println(output);
return;
}
for (int i = 0; i < size; ++i)
{
// Find result using recursion
result(record, output + record[i], n - 1, size);
}
}
public static void main(String[] args)
{
// record element
char[] record = {
'A' , 'B'
};
// Get number of element in record set
int size = record.length;
// Length of generated string
int n = 4;
}
}``````

#### input

``````AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ program
Print all possible strings of length N in a set
*/
class Combinations
{
public: void result(char record[], string output, int n, int size)
{
if (n == 0)
{
// Display output
cout << output << endl;
return;
}
for (int i = 0; i < size; ++i)
{
// Find result using recursion
this->result(record, output  +  record[i], n - 1, size);
}
}
};
int main()
{
// record element
char record[] = {
'A' , 'B'
};
// Get number of element in record set
int size = sizeof(record) / sizeof(record);
// Length of generated string
int n = 4;
return 0;
}``````

#### input

``````AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB``````
``````// Include namespace system
using System;
/*
Csharp program
Print all possible strings of length N in a set
*/
public class Combinations
{
public void result(char[] record, String output, int n, int size)
{
if (n == 0)
{
// Display output
Console.WriteLine(output);
return;
}
for (int i = 0; i < size; ++i)
{
// Find result using recursion
this.result(record, output + record[i], n - 1, size);
}
}
public static void Main(String[] args)
{
// record element
char[] record = {
'A' , 'B'
};
// Get number of element in record set
int size = record.Length;
// Length of generated string
int n = 4;
}
}``````

#### input

``````AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB``````
``````package main
import "fmt"
/*
Go program
Print all possible strings of length N in a set
*/

func result(record[] byte, output string, n int, size int) {
if n == 0 {
// Display output
fmt.Println(output)
return
}
for i := 0 ; i < size ; i++ {
// Find result using recursion
result(record, output + string(record[i]), n - 1, size)
}
}
func main() {

// record element
var record = [] byte {
'A',
'B',
}
// Get number of element in record set
var size int = len(record)
// Length of generated string
var n int = 4
result(record, "", n, size)
}``````

#### input

``````AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB``````
``````<?php
/*
Php program
Print all possible strings of length N in a set
*/
class Combinations
{
public	function result(\$record, \$output, \$n, \$size)
{
if (\$n == 0)
{
// Display output
echo(\$output.
"\n");
return;
}
for (\$i = 0; \$i < \$size; ++\$i)
{
// Find result using recursion
\$this->result(\$record, \$output.strval(\$record[\$i]), \$n - 1, \$size);
}
}
}

function main()
{
// record element
\$record = array('A', 'B');
// Get number of element in record set
\$size = count(\$record);
// Length of generated string
\$n = 4;
}
main();``````

#### input

``````AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB``````
``````/*
Node JS program
Print all possible strings of length N in a set
*/
class Combinations
{
result(record, output, n, size)
{
if (n == 0)
{
// Display output
console.log(output);
return;
}
for (var i = 0; i < size; ++i)
{
// Find result using recursion
this.result(record, output + record[i], n - 1, size);
}
}
}

function main()
{
// record element
var record = ['A', 'B'];
// Get number of element in record set
var size = record.length;
// Length of generated string
var n = 4;
}
main();``````

#### input

``````AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB``````
``````#    Python 3 program
#    Print all possible strings of length N in a set
class Combinations :
def result(self, record, output, n, size) :
if (n == 0) :
#  Display output
print(output)
return

i = 0
while (i < size) :
#  Find result using recursion
self.result(record, output + str(record[i]), n - 1, size)
i += 1

def main() :
#  record element
record = ['A', 'B']
#  Get number of element in record set
size = len(record)
#  Length of generated string
n = 4

if __name__ == "__main__": main()``````

#### input

``````AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB``````
``````#    Ruby program
#    Print all possible strings of length N in a set
class Combinations
def result(record, output, n, size)
if (n == 0)
#  Display output
print(output, "\n")
return
end

i = 0
while (i < size)
#  Find result using recursion
self.result(record, output + record[i].to_s, n - 1, size)
i += 1
end

end

end

def main()
#  record element
record = ['A', 'B']
#  Get number of element in record set
size = record.length
#  Length of generated string
n = 4
end

main()``````

#### input

``````AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB
``````
``````/*
Scala program
Print all possible strings of length N in a set
*/
class Combinations()
{
def result(record: Array[Char], output: String, n: Int, size: Int): Unit = {
if (n == 0)
{
// Display output
println(output);
return;
}
var i: Int = 0;
while (i < size)
{
// Find result using recursion
result(record, output + record(i).toString(), n - 1, size);
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Combinations = new Combinations();
// record element
var record: Array[Char] = Array('A', 'B');
// Get number of element in record set
var size: Int = record.length;
// Length of generated string
var n: Int = 4;
}
}``````

#### input

``````AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB``````
``````import Foundation;
/*
Swift 4 program
Print all possible strings of length N in a set
*/
class Combinations
{
func result(_ record: [Character],
_ output: String, _ n: Int, _ size: Int)
{
if (n == 0)
{
// Display output
print(output);
return;
}
var i: Int = 0;
while (i < size)
{
// Find result using recursion
self.result(record, output + String(record[i]), n - 1, size);
i += 1;
}
}
}
func main()
{
// record element
let record: [Character] = ["A", "B"];
// Get number of element in record set
let size: Int = record.count;
// Length of generated string
let n: Int = 4;
}
main();``````

#### input

``````AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB``````
``````/*
Kotlin program
Print all possible strings of length N in a set
*/
class Combinations
{
fun result(record: Array < Char > ,
output: String, n: Int, size: Int): Unit
{
if (n == 0)
{
// Display output
println(output);
return;
}
var i: Int = 0;
while (i < size)
{
// Find result using recursion
this.result(record, output + record[i].toString(), n - 1, size);
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
// record element
val record: Array < Char > = arrayOf('A', 'B');
// Get number of element in record set
val size: Int = record.count();
// Length of generated string
val n: Int = 4;
}``````

#### input

``````AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB``````

## Time Complexity

The time complexity of this algorithm is exponential since each character in the character set is being recursively appended to the output string for each level of recursion. If the character set size is `M` and the desired string length is `N`, the time complexity can be approximated as `O(M^N)`, where each character has `M` possibilities and the recursion goes to a depth of `N`. Keep in mind that this complexity can grow rapidly as `M` and `N` increase.

## 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