impl Solution {
    pub fn generate_parenthesis(n: i32) -> Vec<String> {
        let mut result = vec![];
        Solution::generate_parenthesis_0(n, &mut "".to_string(), &mut result);
        return result;
    }

    fn valid(cur: &String, n: i32) -> bool {
        let mut sum = 0;
        for c in cur.chars() {
            sum += if c == '(' { 1 } else { -1 };
            if sum > n || sum < 0 {
                return false;
            }
        }
        if cur.len() == (n * 2) as usize {
            return sum == 0;
        }
        return true;
    }

    fn generate_parenthesis_0(n: i32, cur: &mut String, collector: &mut Vec<String>) {
        if cur.len() == (n * 2) as usize {
            collector.push(cur.clone());
            return;
        }
        for c in "()".chars() {
            cur.push(c);
            if Solution::valid(cur, n) {
                Solution::generate_parenthesis_0(n, cur, collector);
            }
            cur.pop();
        }
    }
}