Generate binary strings without adjacent zeros

String Backtracking Bit Manipulation

88.2% acceptance

Feb 25, 2026

280

You are given a positive integer n. A binary string x is valid if all substrings of x of length 2 contain at least one "1". Return all valid strings with length n, in any order.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn valid_strings(n: i32) -> Vec<String> {
    let n = n as usize;
    let mut result = Vec::new();
    Self::backtrack(&mut Vec::new(), n, &mut result);
    result
  }

  fn backtrack(s: &mut Vec<char>, n: usize, result: &mut Vec<String>) {
    if s.len() == n {
      result.push(s.iter().collect());
      return;
    }
    // Append '1' - always valid
    s.push('1');
    Self::backtrack(s, n, result);
    s.pop();
    // Append '0' - only valid if last char is not '0'
    if s.is_empty() || *s.last().unwrap() == '1' {
      s.push('0');
      Self::backtrack(s, n, result);
      s.pop();
    }
  }
}