Generate parentheses

String Dynamic Programming Backtracking

78.3% acceptance

Jan 12, 2026

23131

1076

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn generate_parenthesis(n: i32) -> Vec<String> {
    let mut result = Vec::new();
    let mut current = String::new();
    Self::backtrack_parenthesis(&mut result, &mut current, 0, 0, n);
    result
  }
  
  fn backtrack_parenthesis(result: &mut Vec<String>, current: &mut String, open: i32, close: i32, max: i32) {
    if current.len() == (max * 2) as usize {
      result.push(current.clone());
      return;
    }
    
    if open < max {
      current.push('(');
      Self::backtrack_parenthesis(result, current, open + 1, close, max);
      current.pop();
    }
    
    if close < open {
      current.push(')');
      Self::backtrack_parenthesis(result, current, open, close + 1, max);
      current.pop();
    }
  }
}