Generate all the binary strings of N bits.

Given a positive integer number N. Generate all the binary strings(0 and 1) of N bits.

Case 1
Input: length=2
Output:
0 0
0 1
1 0
1 1

Case 2

Input: length=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

Case 3

Input: length=1

Output:

Algorithm:

We will see two approach of generating the binary string combination.

First approach, where we will form the binary string one by one and once it matches the required length, we will backtrack and switch the binary digit. In this approach, as String is immutable each character we append to a String will create new String object.

Recursive stack trace of Generating all the binary strings of N bits.

generate all binary strings of length n with k bits set

Generate all the binary strings of N bits.

Second approach, In the first approach, each time we append the new character to String, a new String literal is created, so why to waste the space. In this approach we will use the fixed size array so that anytime we iterate and use the array we will always be working on fixed size array.

for more details on String and Memory management in Java, visit Java Memory Management Interview Questions

Java Program to Generate all the binary strings of N bits.

package javabypatel;
 
public class GenerateBinaryString {
 
    public void printBinaryCombination(int length, String str) {
        if (str.length() == length) {
            System.out.println(str);
            return;
        }
        printBinaryCombination(length, str + "0");
        printBinaryCombination(length, str + "1");
    }
 
    public static void main(String[] args) {
        GenerateBinaryString obj = new GenerateBinaryString();
        int length = 3;

        System.out.println("Approach 1");
        obj.printBinaryCombination(length, "");
    }
}

Optimized Approach: Using Array so no new String is created when a character is appended each time

package javabypatel;
 
import java.util.Arrays;
 
public class GenerateBinaryString {
 
    public void printBinaryCombination(int index, int[] arr) {
        if (index == arr.length) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        arr[index] = 0;
        printBinaryCombination(index + 1, arr);
        arr[index] = 1;
        printBinaryCombination(index + 1, arr);
    }
 
    public static void main(String[] args) {
        GenerateBinaryString obj = new GenerateBinaryString();
        int length = 3;
 
        System.out.println("Approach 2");
        obj.printBinaryCombination(0, new int[length]);
    }
}