C program to generate all combinations of N-Bit Binary String

by

Posted on 10 July 2018

In this tutorial, we will learn how to write a c program to print all the combinations of an n-bit binary string. We are going to create a recursive function which will take the length of the string(N) as an input and will print all the possible combinations of the binary string. 

Before diving into the code let's understand how we are going to do this, we are going to take an example of 2-bit binary string so the possible combinations will be.

00 01 10 11

now let's see our function which will print all the combinations and then we will understand how it is going to work.

Also Read: C program to find Modular Multiplicative Inverse of two Relatively Prime Numbers

void Binary(int n){
	if(n<1)
		printf("%s ", A);
	else{
		A[n-1] = '0';
		Binary(n-1);
		A[n-1] = '1';
		Binary(n);
	}
}

At first, it may look a little bit confusing to you but don't worry we are going to explain it to you let say we need to generate all possible combinations of a 2-bit binary string. so let's follow a backward approach since we are using a recursive function.

  • Calling Binary(1)

for n=1, A[n-1] => A[0] = 0, A[0] is set as 0
now Binary(0) is called since the condition (n<1) is true so the output will be printed as 0.

for n=1, A[n-1] => A[0] = 1, A[0] is now set as 1
now Binary(0) is called and since the if condition is true the ouput will be 1.

So for Binary(1) the output is as {0,  1}

  • Calling Binary(2)

for n = 2,  A[n-1] => A[1] = 0, A[1] is set as 0.
now Binary(1) is called but we already know that Binary(1) gives output as {0, 1} for A[0].

So when A[1] will be set as 0 the output will be {00, 01}

for n = 2,  A[n-1] => A[1] = 1, A[1] is set as 1.
now Binary(1) is called and the output for it will be {0, 1}.

So when A[0] will be set as 1 the output will be {10, 11}

The complete output will be {00, 01, 10, 11}.

That was a quick explanation (if you still have any doubts then feel free to ask them in the comments section below), now let's write the C program for the above problem.

C program to find all combinations of n-bit Binary String.

#include<stdio.h>
#define size 10

char A[size];

void Binary(int n){
	if(n<1)
		printf("%s ", A);
	else{
		A[n-1] = '0';
		Binary(n-1);
		A[n-1] = '1';
		Binary(n-1);
	}
}

int main(){
	int n;
	printf("Enter the length of the Binary String: ");
	scanf("%d",&n);
	Binary(n);
	
	return 0;
}

Output

Enter the length of the Binary String: 3
000 001 010 011 100 101 110 111

If You Love this article, You Should Consider:

  • Like us on Facebook
  • Follow us on Instagram
  • Follow us on Twitter
  • Subscribe to our Newsletter.
  • Let us know your suggestions and queries in the comments below.

Thank you for your Love and Support

Share your thoughts

Search
Adverstisement
Adverstisement