Write a c program to generate all strings of n bits by using recursive backtracking method.. For example if given size of an array is 3 then the output should be [0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,10] and [1,1,1].

c program to generate all strings of n bits

#include<stdio.h>

void backtrack(int *arr, int n, int arr_len) {
	//base case
	if (n <= 0) {
		printf("[");
		for (int i = arr_len-1; i >=0; i--) {
			if (i == 0)
				printf("%d", arr[i]);
			else
				printf("%d,", arr[i]);
		}
		printf("]\n");
		return;
	}
	arr[n - 1] = 0;
	backtrack(arr, n - 1, arr_len);
	// backtrack
	arr[n - 1] = 1;
	backtrack(arr, n - 1, arr_len);
}

int main() {
	int n = 3;
	int arr[3];
	backtrack(arr, n, n);
	return 0;
}

How it works

  • We have used backtracking to solve this problem.
  • The length of the nbits string is 3.
  • Every bit of the string has only two option. Either a bit will be 1 or 0.
  • So we have recursively call our function backtrack() and set the bit 0.
  • When base case reached ,we have print the array and return.
  • In the state of return we backtrack by assigning bit to 1.

Note: Generally backtracking method is a complex task to understand. Practicing these types of problem will make you understand backtracking solution.  Try to understand above c program using gdb debugging with pen and paper.



Related Contents to follow