Posted on by Kalkicode
Code Backtracking

# Generate all the binary strings of N bits

The problem at hand is to generate all binary strings of N bits. In other words, given an integer N, we want to create and print all possible combinations of 0s and 1s of length N. For instance, if N = 2, the binary strings generated would be "00", "01", "10", and "11".

## Problem Statement

We need to write a program that generates and prints all possible binary strings of N bits.

## Example

Let's consider N = 3. The expected output would be:

``````000
001
010
011
100
101
110
111``````

## Idea to Solve

The problem can be solved using a recursive approach. At each step, we can either choose to place a '0' or a '1' at the current position of the string. We repeat this process for each position in the string, ultimately generating all possible combinations.

## Pseudocode

Here's the pseudocode for the solution:

``````function generateBinaryStrings(record, start, last):
if start == last:
print record
return
record[start] = '0'
generateBinaryStrings(record, start + 1, last)

record[start] = '1'
generateBinaryStrings(record, start + 1, last)

function binaryString(n):
if n <= 0:
return
create an array record of size n
generateBinaryStrings(record, 0, n)

``````

## Algorithm Explanation

1. The `generateBinaryStrings` function is the heart of our solution. It takes three parameters: `record` (an array to store the binary string being generated), `start` (the current position in the string being processed), and `last` (the total length of the binary string we want to generate).

2. If the `start` index reaches `last`, it means we have filled all positions in the array, and we can print the generated binary string.

3. First, we set the character at the `start` index to '0' and make a recursive call to `generateBinaryStrings` with `start + 1`.

4. Then, we set the character at the `start` index to '1' and make another recursive call to `generateBinaryStrings` with `start + 1`.

5. The `binaryString` function takes an integer `n` as input and acts as a driver function. It checks if `n` is greater than 0 and proceeds to create an array `record` of size `n`.

6. The `binaryString` function then calls `generateBinaryStrings` with `record`, 0 as the starting index, and `n` as the last index.

## Code Solution

``````/*
C program for
Generate all the binary strings of N bits
*/
#include <stdio.h>

void solution(char record[], int start, int last)
{
if (start == last)
{
printf(" %s \n", record);
return;
}
record[start] = '0';
solution(record, start + 1, last);
// change to 1
record[start] = '1';
solution(record, start + 1, last);
}
void binaryString(int n)
{
// N indicate digit in binary
if (n <= 0)
{
return;
}
char record[n];
printf(" Digit : %d \n", n);
solution(record, 0, n);
}
int main(int argc, char const * argv[])
{
// Test
binaryString(4);
return 0;
}``````

#### Output

`````` Digit : 4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111``````
``````/*
Java program for
Generate all the binary strings of N bits
*/
class BinaryText
{
public void solution(String record, int start, int last)
{
if (start == last)
{
System.out.print(" " + record + " \n");
return;
}
// Find result using recursion
solution(record + '0', start + 1, last);
solution(record + '1', start + 1, last);
}
public void binaryString(int n)
{
// N indicate digit in binary
if (n <= 0)
{
return;
}
System.out.print(" Digit : " + n + " \n");
this.solution("", 0, n);
}
public static void main(String[] args)
{
}
}``````

#### Output

`````` Digit : 4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ program for
Generate all the binary strings of N bits
*/
class BinaryText
{
public: void solution(string record, int start, int last)
{
if (start == last)
{
cout << " " << record << " \n";
return;
}
// Find result using recursion
this->solution(record  +  '0', start + 1, last);
this->solution(record  +  '1', start + 1, last);
}
void binaryString(int n)
{
// N indicate digit in binary
if (n <= 0)
{
return;
}
cout << " Digit : " << n << " \n";
this->solution("", 0, n);
}
};
int main()
{
return 0;
}``````

#### Output

`````` Digit : 4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111``````
``````// Include namespace system
using System;
/*
Csharp program for
Generate all the binary strings of N bits
*/
public class BinaryText
{
public void solution(String record, int start, int last)
{
if (start == last)
{
Console.Write(" " + record + " \n");
return;
}
// Find result using recursion
this.solution(record + '0', start + 1, last);
this.solution(record + '1', start + 1, last);
}
public void binaryString(int n)
{
// N indicate digit in binary
if (n <= 0)
{
return;
}
Console.Write(" Digit : " + n + " \n");
this.solution("", 0, n);
}
public static void Main(String[] args)
{
}
}``````

#### Output

`````` Digit : 4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111``````
``````package main
import "fmt"
/*
Go program for
Generate all the binary strings of N bits
*/

func solution(record string, start int, last int) {
if start == last {
fmt.Print(" ", record, " \n")
return
}
// Find result using recursion
solution(record +string('0'), start + 1, last)
solution(record +string('1'), start + 1, last)
}
func binaryString(n int) {
// N indicate digit in binary
if n <= 0 {
return
}
fmt.Print(" Digit : ", n, " \n")
solution("", 0, n)
}
func main() {

binaryString(4)
}``````

#### Output

`````` Digit : 4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111``````
``````<?php
/*
Php program for
Generate all the binary strings of N bits
*/
class BinaryText
{
public	function solution(\$record, \$start, \$last)
{
if (\$start == \$last)
{
echo(" ".\$record.
" \n");
return;
}
// Find result using recursion
\$this->solution(\$record.strval('0'), \$start + 1, \$last);
\$this->solution(\$record.strval('1'), \$start + 1, \$last);
}
public	function binaryString(\$n)
{
// N indicate digit in binary
if (\$n <= 0)
{
return;
}
echo(" Digit : ".\$n.
" \n");
\$this->solution("", 0, \$n);
}
}

function main()
{
}
main();``````

#### Output

`````` Digit : 4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111``````
``````/*
Node JS program for
Generate all the binary strings of N bits
*/
class BinaryText
{
solution(record, start, last)
{
if (start == last)
{
process.stdout.write(" " + record + " \n");
return;
}
// Find result using recursion
this.solution(record + '0', start + 1, last);
this.solution(record + '1', start + 1, last);
}
binaryString(n)
{
// N indicate digit in binary
if (n <= 0)
{
return;
}
process.stdout.write(" Digit : " + n + " \n");
this.solution("", 0, n);
}
}

function main()
{
}
main();``````

#### Output

`````` Digit : 4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111``````
``````#    Python 3 program for
#    Generate all the binary strings of N bits
class BinaryText :
def solution(self, record, start, last) :
if (start == last) :
print(" ", record ," ")
return

#  Find result using recursion
self.solution(record + str('0'), start + 1, last)
self.solution(record + str('1'), start + 1, last)

def binaryString(self, n) :
#  N indicate digit in binary
if (n <= 0) :
return

print(" Digit : ", n ," ")
self.solution("", 0, n)

def main() :

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

#### Output

`````` Digit :  4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111``````
``````#    Ruby program for
#    Generate all the binary strings of N bits
class BinaryText
def solution(record, start, last)
if (start == last)
print(" ", record ," \n")
return
end

#  Find result using recursion
self.solution(record + '0'.to_s, start + 1, last)
self.solution(record + '1'.to_s, start + 1, last)
end

def binaryString(n)
#  N indicate digit in binary
if (n <= 0)
return
end

print(" Digit : ", n ," \n")
self.solution("", 0, n)
end

end

def main()
end

main()``````

#### Output

`````` Digit : 4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
``````
``````/*
Scala program for
Generate all the binary strings of N bits
*/
class BinaryText()
{
def solution(record: String, start: Int, last: Int): Unit = {
if (start == last)
{
print(" " + record + " \n");
return;
}
// Find result using recursion
solution(record + '0'.toString(), start + 1, last);
solution(record + '1'.toString(), start + 1, last);
}
def binaryString(n: Int): Unit = {
// N indicate digit in binary
if (n <= 0)
{
return;
}
print(" Digit : " + n + " \n");
this.solution("", 0, n);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: BinaryText = new BinaryText();
}
}``````

#### Output

`````` Digit : 4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111``````
``````/*
Swift 4 program for
Generate all the binary strings of N bits
*/
class BinaryText
{
func solution(_ record: String, _ start: Int, _ last: Int)
{
if (start == last)
{
print(" ", record ," ");
return;
}
// Find result using recursion
self.solution(record + String("0"), start + 1, last);
self.solution(record + String("1"), start + 1, last);
}
func binaryString(_ n: Int)
{
// N indicate digit in binary
if (n <= 0)
{
return;
}
print(" Digit : ", n ," ");
self.solution("", 0, n);
}
}
func main()
{
}
main();``````

#### Output

`````` Digit :  4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111``````
``````/*
Kotlin program for
Generate all the binary strings of N bits
*/
class BinaryText
{
fun solution(record: String, start: Int, last: Int): Unit
{
if (start == last)
{
print(" " + record + " \n");
return;
}
// Find result using recursion
this.solution(record + '0'.toString(), start + 1, last);
this.solution(record + '1'.toString(), start + 1, last);
}
fun binaryString(n: Int): Unit
{
// N indicate digit in binary
if (n <= 0)
{
return;
}
print(" Digit : " + n + " \n");
this.solution("", 0, n);
}
}
fun main(args: Array < String > ): Unit
{
}``````

#### Output

`````` Digit : 4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111``````

## Time Complexity

The time complexity of this solution is exponential, specifically O(2^n), where n is the number of bits in the binary string. This is because at each position, we have two choices (0 or 1), and we make two recursive calls for each position. The total number of recursive calls made is 2^n, which results in an exponential growth in the number of function calls and operations performed.

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