struct Solution;
impl Solution {
fn generate_parenthesis(n: i32) -> Vec<String> {
let mut res: Vec<String> = vec![];
let mut cur: String = "".to_string();
Self::dfs(n, n, &mut cur, &mut res);
res
}
fn dfs(left: i32, right: i32, cur: &mut String, all: &mut Vec<String>) {
if left == 0 && right == 0 {
all.push(cur.to_string());
} else {
if left > 0 {
cur.push('(');
Self::dfs(left - 1, right, cur, all);
cur.pop();
}
if right > left {
cur.push(')');
Self::dfs(left, right - 1, cur, all);
cur.pop();
}
}
}
}
#[test]
fn test() {
let res: Vec<String> = vec_string!["((()))", "(()())", "(())()", "()(())", "()()()"];
assert_eq!(Solution::generate_parenthesis(3), res);
}