Generate All Strings of n bits.

Objec­tive: Generate All Strings of n bits, consider A[0..n-1] is an array of size n.

Example :

n = 3
Output:
[0, 0, 0]    [1, 0, 0]    [0, 1, 0]    [1, 1, 0]

[0, 0, 1]     [1, 0, 1]     [0, 1, 1]    [1, 1, 1]

Approach:

  • Recursion is key here.
  • create a integer array of size n.
  • Now if we think of every bit, it can take 2 values, 0 and 1.
  • starting from the end of the string, set the bit 0 and 1 and make recursive calls

Time Complexity – O(2^n)
Code:

import java.util.*;
public class NbitsStrings {
int[] arrA;
public NbitsStrings(int n) {
arrA = new int[n];
}
public void nBits(int n) {
if (n <= 0) {
System.out.println(Arrays.toString(arrA));
} else {
arrA[n 1] = 0;
nBits(n 1);
arrA[n 1] = 1;
nBits(n 1);
}
}
public static void main(String[] args) throws java.lang.Exception {
int n = 3;
NbitsStrings i = new NbitsStrings(n);
i.nBits(n);
}
}

view raw
NbitsStrings.java
hosted with ❤ by GitHub


Output:

[0, 0, 0]
[1, 0, 0]
[0, 1, 0]
[1, 1, 0]
[0, 0, 1]
[1, 0, 1]
[0, 1, 1]
[1, 1, 1]