Strobogrammatic Numbers II (Recursion)

XXX. Strobogrammatic Numbers

Recursion

Math

Problem Statement:

Find all strobogrammatic numbers of length n. A strobogrammatic number is a number that looks the same when rotated 180 degrees.

• 1, 8, 0 read same upside down
• 6 becomes 9 when rotated
• 9 becomes 6 when rotated

Implementations:

Java Solution:

public List findStrobogrammatic(int n) {
    return recurse(n, n);
}

public List recurse(int n, int k) {
    List result = new ArrayList<>();
    
    // Base cases
    if (n == 0) {
        result.add("");
        return result;
    }
    
    if (n == 1) {
        result.add("0");
        result.add("1");
        result.add("8");
        return result;
    }
    
    // Get inner numbers recursively
    List list = recurse(n - 2, k);
    
    // Add pairs around each inner number
    for (String s: list) {
        if (n != k) 
            result.add("0" + s + "0");
        result.add("1" + s + "1");
        result.add("8" + s + "8");
        result.add("6" + s + "9");
        result.add("9" + s + "6");
    }
    
    return result;
}

Python Solution:

def findStrobogrammatic(self, n: int) -> List[str]:
    def recurse(n: int, k: int) -> List[str]:
        # Base cases
        if n == 0:
            return [""]
        if n == 1:
            return ["0", "1", "8"]
        
        # Get inner numbers recursively
        inner = recurse(n - 2, k)
        result = []
        
        # Add pairs around each inner number
        for s in inner:
            if n != k:
                result.append(f"0{s}0")
            result.append(f"1{s}1")
            result.append(f"8{s}8")
            result.append(f"6{s}9")
            result.append(f"9{s}6")
        
        return result
    
    return recurse(n, n)

C++ Solution:

class Solution {
public:
    vector findStrobogrammatic(int n) {
        return recurse(n, n);
    }
    
private:
    vector recurse(int n, int k) {
        vector result;
        
        // Base cases
        if (n == 0) {
            result.push_back("");
            return result;
        }
        
        if (n == 1) {
            return {"0", "1", "8"};
        }
        
        // Get inner numbers recursively
        vector list = recurse(n - 2, k);
        
        // Add pairs around each inner number
        for (const string& s : list) {
            if (n != k)
                result.push_back("0" + s + "0");
            result.push_back("1" + s + "1");
            result.push_back("8" + s + "8");
            result.push_back("6" + s + "9");
            result.push_back("9" + s + "6");
        }
        
        return result;
    }
};

Example:

For n = 4:

• Start with n=2 inner numbers: ["", "11","69","88","96"]
• Add pairs around each:
  • "" → "1001", "1111", "6996", "8888", "9669"
  • Continue for other inner numbers
• Note: Leading zeros not allowed for full length

Complexity:

Time Complexity: O(5^(n/2)), 5 choices for each pair
Space Complexity: O(n) for recursion stack

Implementation Notes:

• **Recursive Strategy**:
  • Build from inside out
  • Add matching pairs at each step
  • Track original n for leading zero check
• **Number Properties**:
  • Single digits: 0,1,8
  • Paired digits: 00,11,88,69,96
  • No leading zeros for full number