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 can download the code here.

## 28 comments

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.

Hi Mayank,

Let us try to understand the code.

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.

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

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.

thanks for helping me out.

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.

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?

Time ComÂplexÂity â€” O(2^n)

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

Hi Trisha,

This should help you out

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??

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

Hi Srushtee,

Please check this link for a working version of the code.

I hope this helps you.

http://ideone.com/8xLjSQ

Have you try to run your code?

It print out:

00

10

01

11

rather then sorted order

00

01

10

11

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

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

nikoo,Thanks man ,thanks for the help .

You are most welcome Pradeek.

what exactly is the meaning of this question?

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

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

Hi Robert,

Please check this link for a working version of the code.

I hope this helps you.

http://ideone.com/8xLjSQ

How to get the output in a sorted manner , i.e ,

000

001

010

011

100

101

110

111 ( for length 3 bits)

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

when printing

I hope this helps.

but how please explain using stack frame

Hi Steve,

Let us try to understand the code.

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.

“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

Hi Wally,

Could you please explain more regarding this.