Generate All Binary Strings | Backtracking Approach

Given an integer N , Print all binary strings of size N which do not contain consecutive 1s.

A binary string is that string which contains only 0 and 1.

Here’s the [Problem Link] to begin with.

Example 1:
Input:
N = 3
Output:
000 , 001 , 010 , 100 , 101
Explanation:
None of the above strings contain consecutive 1s. "110" is not an answer as it has '1's occuring consecutively. 

Your Task:

You don’t need to read input or print anything. Your task is to complete the function generateBinaryStrings() which takes an integer N as input and returns a list of all valid binary strings in lexicographically increasing order.

Expected Time Complexity: O(2^N)
Expected Auxiliary Space: O(N)

Constraints:
1 <= N <= 20

Solution: Backtracking Approach

Intuition

Think of this like filling positions in a string one by one, but with a rule: “You can’t place two 1’s next to each other!” It’s like a game where you’re placing 0’s and 1’s, but whenever you place a 1, the next position becomes “dangerous” – you can only put a 0 there. When you place a 0, the next position becomes “safe” again – you can put either 0 or 1. We use backtracking to explore all valid combinations by trying different choices and undoing them when needed.

Detailed Approach

1. Initialize Setup: Create an array of “0”s of length N to represent positions in the binary string.
2. Recursive Function: Use a helper function that takes the current index, a flag indicating if we can place ‘1’, the current string array, and result list.
3. Base Case: When index reaches N, we’ve filled all positions – add the current string to results.
4. Always Try ‘0’: At any position, we can always place ‘0’ (it doesn’t violate the no-consecutive-1’s rule).
5. Conditionally Try ‘1’: Only place ‘1’ if the flag is True (meaning the previous character wasn’t ‘1’).
6. Update Flag: After placing ‘0’, set flag=True for next position. After placing ‘1’, set flag=False for next position.
7. Backtrack: After exploring one choice, reset the position and try other possibilities.

Code

class Solution:
    def solve(self, index, flag, numbers, result):
        # Base case: If we've filled all positions, add to result
        if index >= len(numbers):
            result.append("".join(numbers))  # Convert array to string
            return
        
        # Choice 1: Always place '0' at current position
        numbers[index] = "0"
        self.solve(index + 1, True, numbers, result)  # Next position can have 0 or 1
        
        # Choice 2: Place '1' only if flag is True (no consecutive 1's)
        if flag == True:
            numbers[index] = "1"
            self.solve(index + 1, False, numbers, result)  # Next position can only have 0
            numbers[index] = "0"  # Backtrack: reset to "0" for clean slate

    def generateBinaryStrings(self, n):
        numbers = ["0"] * n  # Initialize array with all "0"s
        result = []          # List to store all valid binary strings
        self.solve(0, True, numbers, result)  # Start from index 0, flag=True
        return result

Code Explanation

The solve function builds binary strings recursively while maintaining the no-consecutive-1’s constraint using the flag parameter. At each position, it first tries placing ‘0’ (always allowed) and recurses with flag=True, meaning the next position can have either 0 or 1. Then, if the flag is True (previous character wasn’t ‘1’), it tries placing ‘1’ and recurses with flag=False, meaning the next position can only have ‘0’. The backtrack step numbers[index] = "0" ensures we clean up after trying ‘1’ so other branches aren’t affected. When we reach the end, we join the array into a string and add it to results.

Dry Run

Let’s trace through N=3:

Start: index=0, flag=True, numbers=[“0″,”0″,”0”]

Branch 1: Place ‘0’ at index 0

• numbers=[“0″,”0″,”0”], recurse with index=1, flag=TrueBranch 1.1: Place ‘0’ at index 1
  • numbers=[“0″,”0″,”0”], recurse with index=2, flag=TrueBranch 1.1.1: Place ‘0’ at index 2
    • numbers=[“0″,”0″,”0”], index=3 → add “000” to result
    Branch 1.1.2: Place ‘1’ at index 2 (flag=True)
    • numbers=[“0″,”0″,”1”], index=3 → add “001” to result
    • Backtrack: numbers=[“0″,”0″,”0”]
  Branch 1.2: Place ‘1’ at index 1 (flag=True)
  • numbers=[“0″,”1″,”0”], recurse with index=2, flag=FalseBranch 1.2.1: Place ‘0’ at index 2 only (flag=False)
    • numbers=[“0″,”1″,”0”], index=3 → add “010” to result
    • Backtrack: numbers=[“0″,”0″,”0”]

Branch 2: Place ‘1’ at index 0 (flag=True)

• numbers=[“1″,”0″,”0”], recurse with index=1, flag=FalseBranch 2.1: Place ‘0’ at index 1 only (flag=False)
  • numbers=[“1″,”0″,”0”], recurse with index=2, flag=TrueBranch 2.1.1: Place ‘0’ at index 2
    • numbers=[“1″,”0″,”0”], index=3 → add “100” to result
    Branch 2.1.2: Place ‘1’ at index 2 (flag=True)
    • numbers=[“1″,”0″,”1”], index=3 → add “101” to result

Result: ["000", "001", "010", "100", "101"]

Time and Space Complexity

• Time Complexity: O(2^n) – In the worst case, we might explore up to 2^n combinations, though the constraint reduces the actual number significantly.
• Space Complexity: O(n) – The recursion stack depth is n, plus space for the numbers array.

Simplifying It

This backtracking approach is like playing a careful game where you fill positions one by one with a safety rule. The flag acts like a traffic light: green (True) means you can place either 0 or 1, red (False) means you can only place 0. Every time you place a 1, you turn the next light red to prevent consecutive 1’s. The backtracking ensures you try all valid combinations systematically, and the recursive structure naturally generates all possibilities without missing any or creating duplicates.

The key insight is using the flag to track the constraint state, making it easy to enforce the “no consecutive 1’s” rule without complex checking logic. This pattern works great for constraint-based string generation problems!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.