Given a positive integer number N. The task is to generate all the binary strings of N bits. These binary strings should be in ascending order.
Examples:
Input: 2
Output:
0 0
0 1
1 0
1 1
Input: 3
Output:
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Approach: The idea is to try every permutation. For every position, there are 2 options, either β0β or β1β. Backtracking is used in this approach to try every possibility/permutation.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void printTheArray( int arr[], int n)
{
for ( int i = 0; i < n; i++) {
cout << arr[i] << " " ;
}
cout << endl;
}
void generateAllBinaryStrings( int n, int arr[], int i)
{
if (i == n) {
printTheArray(arr, n);
return ;
}
arr[i] = 0;
generateAllBinaryStrings(n, arr, i + 1);
arr[i] = 1;
generateAllBinaryStrings(n, arr, i + 1);
}
int main()
{
int n = 4;
int arr[n];
generateAllBinaryStrings(n, arr, 0);
return 0;
}
|
Java
import java.util.*;
class GFG
{
static void printTheArray( int arr[], int n)
{
for ( int i = 0 ; i < n; i++)
{
System.out.print(arr[i]+ " " );
}
System.out.println();
}
static void generateAllBinaryStrings( int n,
int arr[], int i)
{
if (i == n)
{
printTheArray(arr, n);
return ;
}
arr[i] = 0 ;
generateAllBinaryStrings(n, arr, i + 1 );
arr[i] = 1 ;
generateAllBinaryStrings(n, arr, i + 1 );
}
public static void main(String args[])
{
int n = 4 ;
int [] arr = new int [n];
generateAllBinaryStrings(n, arr, 0 );
}
}
|
Python3
def printTheArray(arr, n):
for i in range ( 0 , n):
print (arr[i], end = " " )
print ()
def generateAllBinaryStrings(n, arr, i):
if i = = n:
printTheArray(arr, n)
return
arr[i] = 0
generateAllBinaryStrings(n, arr, i + 1 )
arr[i] = 1
generateAllBinaryStrings(n, arr, i + 1 )
if __name__ = = "__main__" :
n = 4
arr = [ None ] * n
generateAllBinaryStrings(n, arr, 0 )
|
C#
using System;
class GFG
{
static void printTheArray( int []arr, int n)
{
for ( int i = 0; i < n; i++)
{
Console.Write(arr[i]+ " " );
}
Console.WriteLine();
}
static void generateAllBinaryStrings( int n,
int []arr, int i)
{
if (i == n)
{
printTheArray(arr, n);
return ;
}
arr[i] = 0;
generateAllBinaryStrings(n, arr, i + 1);
arr[i] = 1;
generateAllBinaryStrings(n, arr, i + 1);
}
public static void Main(String []args)
{
int n = 4;
int [] arr = new int [n];
generateAllBinaryStrings(n, arr, 0);
}
}
|
Javascript
<script>
function printTheArray(arr, n)
{
for (let i = 0; i < n; i++)
{
document.write(arr[i]+ " " );
}
document.write( "</br>" );
}
function generateAllBinaryStrings(n, arr, i)
{
if (i == n)
{
printTheArray(arr, n);
return ;
}
arr[i] = 0;
generateAllBinaryStrings(n, arr, i + 1);
arr[i] = 1;
generateAllBinaryStrings(n, arr, i + 1);
}
let n = 4;
let arr = new Array(n);
arr.fill(0);
generateAllBinaryStrings(n, arr, 0);
</script>
|
PHP
<?php
function printTheArray( $arr , $n )
{
for ( $i = 0; $i < $n ; $i ++)
{
echo $arr [ $i ], " " ;
}
echo "\n" ;
}
function generateAllBinaryStrings( $n , $arr , $i )
{
if ( $i == $n )
{
printTheArray( $arr , $n );
return ;
}
$arr [ $i ] = 0;
generateAllBinaryStrings( $n , $arr , $i + 1);
$arr [ $i ] = 1;
generateAllBinaryStrings( $n , $arr , $i + 1);
}
$n = 4;
$arr = array_fill (0, $n , 0);
generateAllBinaryStrings( $n , $arr , 0);
?>
|
Output
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
Time complexity β O(2n)
Space complexity β O(n)
Approach 2: Bit Manipulation
Step-by-step Explanation:
- Generate all numbers from 0 to 2^n β 1.
- Convert each number to its binary representation using the bitset class from the C++ Standard Library.
- Extract the last n bits of the binary representation using the substr method.
C++
#include <iostream>
#include <bitset>
using namespace std;
int main() {
int n = 4;
for ( int i = 0; i < (1 << n); i++) {
bitset<32> b(i);
cout << b.to_string().substr(32-n) << endl;
}
return 0;
}
|
Java
public class Main {
public static void main(String[] args)
{
int n = 4 ;
for ( int i = 0 ; i < ( 1 << n); i++) {
String binaryString = toBinaryString(i, n);
System.out.println(binaryString);
}
}
static String toBinaryString( int num, int length)
{
StringBuilder sb = new StringBuilder();
for ( int i = length - 1 ; i >= 0 ; i--) {
int bit = (num & ( 1 << i)) >> i;
sb.append(bit);
}
return sb.toString();
}
}
|
Python
def print_binary_combinations(n):
for i in range ( 1 << n):
binary_str = format (i, '0' + str (n) + 'b' )
print (binary_str)
n = 4
print_binary_combinations(n)
|
C#
using System;
class GFG {
static void Main()
{
int n = 4;
for ( int i = 0; i < (1 << n); i++) {
string binary
= Convert.ToString(i, 2).PadLeft(n, '0' );
Console.WriteLine(binary);
}
}
}
|
Javascript
<script>
const n = 4;
for (let i = 0; i < (1 << n); i++) {
const binaryString = (i >>> 0).toString(2).padStart(n, '0' );
console.log(binaryString);
}
</script>
|
Output
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Time Complexity: O(n * 2^n)
Auxiliary Space: O(n)
The time complexity is O(n * 2^n) because we need to generate all 2^n binary strings and each binary string has a length of n. The auxiliary space complexity is O(n) because we need to store the binary representation of each number.
How is this approach different from another approach?
This approach is different from the recursive approach because it uses bit manipulation to generate all binary strings instead of recursion. The recursive approach has a time complexity of O(2^n) and an auxiliary space complexity of O(n), while this approach has a time complexity of O(n * 2^n) and an auxiliary space complexity of O(n).