Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Generate All Strings of n bits.

Objec­tive: - Gen­er­ate All Strings of n bits, con­sider A[0..n-1] is an array of size n.

Exam­ple :

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:

  • Recur­sion is key here.
  • cre­ate a inte­ger array of size n.
  • Now if we think of every bit, it can take 2 val­ues, 0 and 1.
  • start­ing from the end of the string, set the bit 0 and 1 and make recur­sive calls

Time Com­plex­ity — O(2^n)
Code:

Out­put:

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

You may also like...