22. Generate Parentheses

Description of Problem

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

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

Solution

Tags: Backtracking

Code (Rust)

impl Solution {
    pub fn generate_parenthesis(n: i32) -> Vec<String> {
        let mut ans = vec![];
        let mut current_string = String::from("");
        Self::dfs(0 , 0, n,  &mut current_string, &mut ans);
        return ans;
    }

    fn dfs(open : i32, close : i32, n : i32, current_string : &mut String , ans : &mut Vec<String>) {
        if open == n && close == n {
            ans.push(current_string.clone());
            return;
        // It's just a speed-up. Remove this block is also okay
        } else if close > open {
            return;
        } 
        
        // Open a parenthesis
        if open < n {
            current_string.push('(');
            Self::dfs(open+1, close, n, current_string, ans);    
            current_string.pop();
        }
        
        // Close a parenthsis
        if close < n && close < open {
            current_string.push(')');
            Self::dfs(open, close + 1, n, current_string, ans); 
            current_string.pop();
        }
    }
}