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

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

 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)
	{
		BinaryText task = new BinaryText();
		task.binaryString(4);
	}
}

 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()
{
	BinaryText *task = new BinaryText();
	task->binaryString(4);
	return 0;
}

 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)
	{
		BinaryText task = new BinaryText();
		task.binaryString(4);
	}
}

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

 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()
{
	$task = new BinaryText();
	$task->binaryString(4);
}
main();

 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()
{
	var task = new BinaryText();
	task.binaryString(4);
}
main();

 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() :
	task = BinaryText()
	task.binaryString(4)

if __name__ == "__main__": main()

 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() 
	task = BinaryText.new()
	task.binaryString(4)
end

main()

 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();
		task.binaryString(4);
	}
}

 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()
{
	let task: BinaryText = BinaryText();
	task.binaryString(4);
}
main();

 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
{
	val task: BinaryText = BinaryText();
	task.binaryString(4);
}

 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.