How to useBacktracking in Javascript
In this approach, we utilize backtracking to generate all binary strings of size K without consecutive 1’s. We start with an empty string and recursively explore all possible choices for each position in the string, ensuring that we append ‘0’ or ‘1’ only if it does not result in consecutive 1’s.
Example:
function generateBinaryStrings(K) {
let results = [];
function backtrack(str, index) {
if (str.length === K) {
results.push(str);
return;
}
// If the last character is '1', we can only append '0'
if (str[str.length - 1] === '1') {
backtrack(str + '0', index + 1);
}
// Otherwise, we can append either '0' or '1'
else {
backtrack(str + '0', index + 1);
backtrack(str + '1', index + 1);
}
}
// Start backtracking from an empty string
backtrack('', 0);
return results.join(' ');
}
console.log(generateBinaryStrings(4));
Output
0000 0001 0010 0100 0101 1000 1001 1010
JavaScript Program to Generate all Binary Strings Without Consecutive 1’s
Given an integer, K. Generate all binary strings of size k without consecutive 1’s.
Examples:
Input : K = 3
Output : 000 , 001 , 010 , 100 , 101
Input : K = 4
Output: 0000 0001 0010 0100 0101 1000 1001 1010
Table of Content
- Approach 1: Using Recursive Function
- Approach 2: Using Stack Data Structure
- Approach 3: Using Iteration and padStart() Method
- Approach 4: Using Backtracking
So, let’s see each of the approaches with its practical implementation.