# 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:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

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

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]
```

### 1 thought on “Generate All Strings of n bits.”

1. Hi,

I’m told that backtracking is used here.Can someone please explain me how backtracking is done here??