Home Theory Generate All Strings of ‘n’ bits. Assume A[0….n-1] be an array of size n.

# Generate All Strings of ‘n’ bits. Assume A[0….n-1] be an array of size n.

void binary(int n)
{
if(n < 1)
printf("%s\n",A);    // Assume A is a global variable
else
{
A[n-1] = '0';
binary(n-1);
A[n-1] = '1';
binary(n-1);
}
}


So if you supply n = 4 in the function what you get as the output is this.

0000
1000
0100
1100
0010
1010
0110
1110
0001
1001
0101
1101
0011
1011
0111
1111

#### You may also like

September 9, 2017 - 02:08

Hi Nikoo,

Could you please explain exactly where are we going back to the track …I understand this problem completely however I am new to backtracking and not able to figure out exactly at what point we are backtracking.

September 9, 2017 - 07:03

Hi Mayank,

Let us try to understand the code.

if(n < 1)
printf("%s\n",arr);
else
{
arr[n-1] = '0';
binary(n-1);
arr[n-1] = '1';
binary(n-1);
}


We will follow a backwards approach since it is a recursive function.For instance lets say n = 1,

The method is called as binary(1);
arr[n-1] is set as ‘0’ (arr[1-1] = arr[0] = ‘0’)

Now we call binary(0);
since (n<1) we print arr (0 is printed)

The call returns to arr[n-1] = ‘1’
arr[1-1] is set as ‘1’ (arr[1-1] = arr[0] = ‘1’)

Now we call binary(0);
since (n<1) we print arr (1 is printed)

Thus, we got 2 outputs as possible bits 0 and 1.

Now let us suppose n = 2,

The method is called as binary(2)
arr[2-1] is set as ‘0’ (arr[2-1] = arr[1] = ‘0’)

Now we call binary(1);
From the above explanation we know that binary(1) produces an output of 0 and 1 for arr[0].
Here arr[1] is set as 0. So we get the 2 outputs (00 and 01).

The function returns to arr[n-1] = ‘1’
arr[2-1] is set as 1 (arr[2-1] = arr[1] = ‘1’)

Again we call binary(1);
This time arr[1] is set as ‘1’ and thus we get 2 more outputs (10 and 11).

We have a total of 4 outputs on screen..(00, 01, 10, 11) These are all the strings of 2 bits.

Similarly, you can work around for n = 3.
arr[2] is set as ‘0’ and binary(2) is called. This produces (000, 010, 100, 110)
arr[2] is then set as ‘1’ and binary(2) is called. This produces (001, 011, 101, 111).
These are all the strings of 3 bits.

I hope this methodology makes it clear. Please feel free to ask anything else as well.

May 12, 2017 - 01:53

my code is not working. can you help me out in my code-

#include
using namespace std;
int a[4];
void binary(int n)
{
if(n&lt;1)
cout<<a<<endl;
else
{
a[n-1]=0;
binary(n-1);
a[n-1]=0;
binary(n-1);
}
}
int main()
{
int num;
cout<>num;
binary(num);
return 0;
}

May 12, 2017 - 13:56

Hi Pulkit,

Your code will not work as you have created an integer array. This is not the same as creating the character array. Please go through the code snippet I have posted once again.

May 12, 2017 - 14:06

thanks for helping me out.

May 12, 2017 - 14:58

sir.
can you explain me how this code works with an example-
void k-string(int n, int k)
{
if(n<1)
printf("%s", a); //consider array a as a global variable
else{
for(int j=0;j<k;j++)
{
a[n-1]=j;
k-string(n-1,k);
}
}
}
this code is generate all the string of length n drawn from 0…..k-1.

February 8, 2017 - 08:27

What is the complexity of this code?
Is it O(2^n) or O(n*2^n), as we are printing the string, so it should take O(n) time?

March 8, 2017 - 12:44

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

November 22, 2016 - 00:40

how the logic can be enhanced to handle a finite alphabet such as {A, T, G, C}.

November 22, 2016 - 09:14

Hi Trisha,

// C program to print all permutations with duplicates allowed
#include <stdio.h>
#include <string.h>

/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}

/* Function to print permutations of string
This function takes three parameters:
1. String
2. Starting index of the string
3. Ending index of the string. */
void permute(char *a, int l, int r)
{
int i;
if (l == r)
printf("%s\n", a);
else
{
for (i = l; i <= r; i++)
{
swap((a+l), (a+i));
permute(a, l+1, r);
swap((a+l), (a+i)); //backtrack
}
}
}

/* Driver program to test above functions */
int main()
{
char str[] = "ABC";
int n = strlen(str);
permute(str, 0, n-1);
return 0;
}

November 22, 2016 - 20:14

thank u.. i have to Develop a computer program to list all the r-combinations from a set of n elements using bitstring representation.. how can that be done??

July 2, 2016 - 12:29

can you please tell me how to initialize this A array?

November 22, 2016 - 09:12

Hi Srushtee,

I hope this helps you.

http://ideone.com/8xLjSQ

May 31, 2016 - 13:52

Have you try to run your code?

It print out:
00
10
01
11

rather then sorted order
00
01
10
11

June 1, 2016 - 16:22

The problem statements never says that the output has to be in sorted order.
It just says to print all the possible combinations.

You are free to post the code that prints in sorted order though :)

October 28, 2015 - 09:32

Great explanation .. Please keep posting code along with such good explanation ..

March 21, 2015 - 06:29

nikoo,Thanks man ,thanks for the help .

March 21, 2015 - 12:38

December 19, 2014 - 18:24

what exactly is the meaning of this question?

December 29, 2014 - 20:19

Hi Ryan,
How many strings can you form using just 1 bit? 0 and 1..right?
How many strings can you form using 2 bits? 00, 01, 10 and 11..right?
So, in this question, you need to generate all the strings of ‘n’ bits. This is it :)

November 7, 2014 - 23:58

Is it possible to make it work where you can input the length from the main function instead of only four? All my attempts have failed

November 8, 2014 - 02:29

Hi Robert,

I hope this helps you.

http://ideone.com/8xLjSQ

October 1, 2014 - 08:59

How to get the output in a sorted manner , i.e ,
000
001
010
011
100
101
110
111 ( for length 3 bits)

October 1, 2014 - 19:35

Hi Thilak,

The output you get is already in sorted order.
To get it in the fashion you have stated, you just need to reverse the string before printing it.

Have a look at this post-
https://studyalgorithms.com/string/print-reverse-of-a-string-using-recursion/

Thus, you can simply call this function

void reversePrint(char *str)
{
while(*str != '\0')
{
reversePrint(str+1);

printf("%c",str);
}
}


when printing

if(n < 1)
{
// printf("%s\n",A);
reversePrint(A);

printf("\n");  // Change the line
}


I hope this helps.

August 14, 2014 - 10:31

but how please explain using stack frame

August 16, 2014 - 23:53

Hi Steve,

Let us try to understand the code.

if(n < 1)
printf("%s\n",arr);
else
{
arr[n-1] = '0';
binary(n-1);
arr[n-1] = '1';
binary(n-1);
}


We will follow a backwards approach since it is a recursive function.For instance lets say n = 1,

The method is called as binary(1);
arr[n-1] is set as ‘0’ (arr[1-1] = arr[0] = ‘0’)

Now we call binary(0);
since (n<1) we print arr (0 is printed)

The call returns to arr[n-1] = ‘1’
arr[1-1] is set as ‘1’ (arr[1-1] = arr[0] = ‘1’)

Now we call binary(0);
since (n<1) we print arr (1 is printed)

Thus, we got 2 outputs as possible bits 0 and 1.

Now let us suppose n = 2,

The method is called as binary(2)
arr[2-1] is set as ‘0’ (arr[2-1] = arr[1] = ‘0’)

Now we call binary(1);
From the above explanation we know that binary(1) produces an output of 0 and 1 for arr[0].
Here arr[1] is set as 0. So we get the 2 outputs (00 and 01).

The function returns to arr[n-1] = ‘1’
arr[2-1] is set as 1 (arr[2-1] = arr[1] = ‘1’)

Again we call binary(1);
This time arr[1] is set as ‘1’ and thus we get 2 more outputs (10 and 11).

We have a total of 4 outputs on screen..(00, 01, 10, 11) These are all the strings of 2 bits.

Similarly, you can work around for n = 3.
arr[2] is set as ‘0’ and binary(2) is called. This produces (000, 010, 100, 110)
arr[2] is then set as ‘1’ and binary(2) is called. This produces (001, 011, 101, 111).
These are all the strings of 3 bits.

I hope this methodology makes it clear. Please feel free to ask anything else as well.

May 26, 2016 - 12:16

“We have a total of 4 outputs on screen..(00, 01, 10, 11) These are all the strings of 2 bits.”

No, this would not be the output…the output would be in this order
00, 10, 01, 11

1) Setting both the bits to 0 and base case printing 00
2) Stack unwind to set Bit 0 to 1 and call binary(n-1) again gives 10
3) Now unwind again setting Bit 1 to 1, which calls binary and sets bit 0 to 0 first and then recurse to base case…gives 01
4) unwind in #3 to give 11

“The output you get is already in sorted order.”
Neither is the output sorted

May 27, 2016 - 10:41

Hi Wally,

Could you please explain more regarding this.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More