impl Solution {
    fn generate_parenthesis(n: i32) -> Vec<String> {
        let mut result = Vec::new();
        Solution::backtrack(&mut result, String::new(), 0, 0, n);
        result
    }

    fn backtrack(result: &mut Vec<String>, current: String, open: i32, close: i32, max: i32) {
        // Base case: if the length of the current string is 2 * max, add it to the results
        if current.len() as i32 == max * 2 {
            result.push(current);
            return;
        }

        // If the number of open parentheses is less than max, add an open parenthesis and recurse
        if open < max {
            let mut new_current = current.clone();
            new_current.push('(');
            Solution::backtrack(result, new_current, open + 1, close, max);
        }

        // If the number of close parentheses is less than open parentheses, add a close parenthesis and recurse
        if close < open {
            let mut new_current = current.clone();
            new_current.push(')');
            Solution::backtrack(result, new_current, open, close + 1, max);
        }
    }
}