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:
0
1
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 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]);
}
}
You may also like to see
Write a program to print all permutations of a given string without repetition. (Repetition of characters is not allowed).
Write a program to print all permutations of a given string with repetition. (Repetition of characters is allowed).
Print all subsets of a given set.
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
