# c program to generate all strings of n bits ( Backtracking problem)

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.*

## Leave a Reply