Backtracking

Backtracking seems confusing and difficult to learn, because there are so many different ways of doing the same thing.

Here, we solve the same problem in many different ways only to see the possibilities.

There is no staisfying and clear definition of backtracking I have found yet. I like to define it as an exhaustive search technique where you make a choice, explore that choice and then undo the choice (backtrack) to make another choice.

This act of making a choice and undoing it is backtracking.

It looks very much like a depth first tree traversal (or graph) traversal with state management.

Problem: Generate N-bit Binary Numbers

Given an integer n, generate all possible binary numbers of length n and return them as a list of strings.

Examples:

Input: n = 2
Output: ["00", "01", "10", "11"]

Input: n = 3
Output: ["000", "001", "010", "011", "100", "101", "110", "111"]

Constraints:

• 1 ≤ n ≤ 16
• The result list should be in lexicographically sorted order
• Each binary number in the output should be exactly n digits long (pad with leading zeros if necessary)

Implementation Approaches

Approach 0: Pure Recursion

Uses recursive decomposition without backtracking. Each recursive call returns its own result list.

"""
Recursive Decomposition- There is no need to maintain a path in this implementation. Therefore, no backtracking is required.
"""
def generate(n) : 
    """
    Eg : For n = 3 , We have 3 spots each of which can be filled with 0 or 1.

    -    -   -
    1/0
         1/0  
             1/0

    1 1 1
    1 1 0
    1 0 1
    1 0 0
    0 1 1
    0 1 0
    0 0 1
    0 0 0 
    """
    if n == 0 : 
        return [""]
    # Recursively generate the binary numbers for n-1 bits
    # generate(n-1) returns a list of binary numbers of length n-1
    # We will take each of these binary numbers and prepend '1' and '0' to each of them
    l = [ "1" + _ for _ in  generate(n-1) ] 
    r = [ "0" + _ for _ in  generate(n-1) ]

    print(f"n = {n} , l = {l} , r = {r}")
    #Concatenate the two lists
    return l + r  

print(generate(3))

This approach: - Uses pure recursive decomposition - Each call builds its own result independently - No need for global state or backtracking - More intuitive but less memory efficient - Time: O(2^n), Space: O(2^n) due to string copies

Approach 1: Pre-allocated Array

Uses a fixed-size array with direct index assignments. Most memory efficient for known size problems.

"""
Backtracking Implementation Using Pre-allocated Array Strategy
Key Features:
- Uses fixed-size array instead of growing/shrinking structure
- No push/pop operations needed
- Memory efficient as array size is known upfront
- Implicit undoing of choices through overwriting
"""
def generate(n) : 
    """
    Implementation Notes:
    1. Pre-allocated array of size 'n' with None values
    2. Each position directly overwritten with 0 or 1
    3. No need for explicit undo operations
    4. More efficient than stack-based approaches for known size problems

    Memory Layout (n=3):
    Initial: [None, None, None]
    During:  ['0'/'1', '0'/'1', '0'/'1']

    Time Complexity: O(2^n) - must generate all binary numbers
    Space Complexity: O(n) - fixed size array, no additional growth
    """

    # Pre-allocate array of size n - more efficient than growing/shrinking a list
    path = [None] * n
    res = []

    #choose  0 or 1 at idx
    def backtrack(idx) : 
        if idx == len(path): 
            res.append("".join(path[:]))
            return 
        # Direct assignment to index - no push/pop needed
        path[idx] = '0'
        backtrack(idx+1)
        # No explicit undo needed - next assignment overwrites

        path[idx] = '1'
        backtrack(idx+1)
        # No explicit undo needed at end - array will be reused

    backtrack(0)
    return res

print(generate(4))

Approach 2: Stack-based with Dual Recursion

Uses explicit push/pop operations with two separate recursive calls for '0' and '1'.

"""
Generate n-bit binary numbers using backtracking.
Implementation Strategy: Stack-based Backtracking 
- Uses list as stack for building binary numbers
- For each position, we make TWO recursive calls because:
  1. First recursive call explores path after choosing '0'
  2. Second recursive call explores path after choosing '1'
- This creates a binary tree where each node represents a digit position
  and has exactly two children (one for '0' and one for '1')
"""
def generate(n) : 
    """
    Decision Tree Shows Two Branches at Each Level:
    Root
    ├── 0 (First recursive call)
    │   ├── 00
    │   └── 01
    └── 1 (Second recursive call)
        ├── 10
        └── 11

    Two Recursive Calls Pattern:
    1. First Call (with '0'): Explores all possibilities starting with '0'
    2. Second Call (with '1'): Explores all possibilities starting with '1'

    This ensures we generate ALL possible combinations systematically
    """

    path = [] #We will treat this as a stack in this implementation
    res = []

    #choose  0 or 1 at idx
    def backtrack(idx) : 
        if idx == n: 
            res.append("".join(path[:]))
            return 

        # First Recursive Branch: Try '0' at current position
        path.append('0')
        backtrack(idx+1)  # Explore all possibilities after choosing '0'
        path.pop()        # Backtrack by removing '0'

        # Second Recursive Branch: Try '1' at current position
        path.append('1')
        backtrack(idx+1)  # Explore all possibilities after choosing '1'
        path.pop()        # Backtrack by removing '1'

    backtrack(0)
    return res

print(generate(3))

Approach 3: For-loop Choices

Uses iteration over choices, making it more extensible for problems with multiple choices.

"""
Generate n-bit binary numbers using backtracking with for-loop iteration.
Implementation Strategy: For-loop Based Choice Selection
- Uses pre-allocated array like version 2
- Iterates over choices using for-loop instead of explicit recursive calls
- More generalizable pattern that can handle multiple choices beyond just binary
- Common pattern in backtracking problems where we iterate over available choices
"""
def generate(n) : 
    """
    Key Differences from Other Versions:
    1. Uses for-loop to iterate over choices ['0','1']
    2. Single recursive call instead of multiple explicit ones
    3. More extensible - easy to add more choices if needed
    4. Common pattern seen in other backtracking problems like:
       - Generating permutations (choices are remaining numbers)
       - N-Queens (choices are valid positions)
       - Sudoku (choices are valid digits)

    Memory Layout:
    - Pre-allocated array: [None] * n
    - Choices handled by for-loop: for choice in ['0','1']
    - Implicit undo through overwriting
    """

    path = [None] * n
    res = []

    #choose  0 or 1 at idx
    def backtrack(idx) : 
        if idx == len(path): 
            res.append("".join(path[:]))
            return 
        for choice in ['0','1'] : 
            path[idx] = choice
            backtrack(idx+1)
            #Here we dont care if path[idx] overwritten,
            #Undo of choice is implicit

    backtrack(0)
    return res

print(generate(3))

Approach 4: Dynamic Stack with For-loop

Combines dynamic stack operations with for-loop choice iteration for clearer state management.

"""
Backtracking with Dynamic Stack & For-loop Choices
Key Features:
- Combines dynamic stack operations (like version 3) with for-loop choice iteration (like version 4)
- Explicit undo operations through pop() (unlike version 2 & 4's implicit overwrites)
- More verbose but clearer state management
- Shows complete choice-explore-undo cycle explicitly
"""
def generate(n) : 
    """
    Implementation Characteristics:
    1. Dynamic Growth: path grows/shrinks as we make/undo choices
    2. Explicit State Management:
       - Choice: path.append(choice)
       - Explore: backtrack(idx+1)
       - Undo: path.pop()
    3. Uses for-loop for choices (more flexible than dual recursion)
    4. Memory Usage: O(n) but with dynamic resizing overhead

    Choice-Explore-Undo Pattern:
    For each position:
        For each choice (0,1):
            1. Make choice (append)
            2. Explore further (recurse)
            3. Undo choice (pop)
    """

    path = []  # We will treat this like a stack in this implementation
    res = []

    #choose  0 or 1 at idx
    def backtrack(idx) : 
        if idx == n: 
            res.append("".join(path[:]))
            return 
        for choice in ['0','1'] : 
            # State Change: Add choice to current path
            path.append(choice)
            # Explore: Recurse with this choice in place
            backtrack(idx+1)
            # State Restoration: Remove choice before next iteration
            path.pop()  # Explicit undo - different from array overwrite versions

    backtrack(0)
    return res

print(generate(3))

Comparison of Approaches

Approach	Memory Usage	State Management	Extensibility	Code Clarity
Pure Recursion	O(2^n)	None (functional)	Limited	Excellent
Pre-allocated Array	Most efficient (O(n) fixed)	Implicit (overwrites)	Limited	Good
Stack with Dual Recursion	O(n) with resizing	Explicit (push/pop)	Limited	Very Good
For-loop Choices	O(n) fixed	Implicit (overwrites)	Excellent	Good
Dynamic Stack with For-loop	O(n) with resizing	Most explicit	Excellent	Excellent

Key Takeaways

1. Pure Recursion: Intuitive but least memory efficient. No bactracking involved.
2. Pre-allocated Array: Best for memory efficiency when size is known
3. Stack with Dual Recursion: Most intuitive for binary choices
4. For-loop Choices: Most extensible for varying number of choices
5. Dynamic Stack with For-loop: Best balance of clarity and flexibility