leetcode/
gen_parentheses.rs

1//! # 22. 括号生成
2//!
3//! 难度 中等
4//!
5//! 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
6//!
7//! ## 示例：
8//!
9//! ```text
10//! 输入：n = 3
11//! 输出：[
12//!        "((()))",
13//!        "(()())",
14//!        "(())()",
15//!        "()(())",
16//!        "()()()"
17//!      ]
18//! ```
19//!
20//! See [leetcode](https://leetcode-cn.com/problems/generate-parentheses/)
21pub struct Solution;
22impl Solution {
23    pub fn generate_parenthesis(n: i32) -> Vec<String> {
24        let mut res = vec![];
25        Self::dfs(0, 0, n, &mut String::new(), &mut res);
26        res
27    }
28
29    fn dfs(left: i32, right: i32, n: i32, chars: &mut String, res: &mut Vec<String>) {
30        if chars.len() == n as usize * 2 {
31            res.push(chars.clone());
32            return;
33        }
34        if left < n {
35            chars.push('(');
36            Self::dfs(left + 1, right, n, chars, res);
37            chars.pop();
38        }
39        if right < left {
40            chars.push(')');
41            Self::dfs(left, right + 1, n, chars, res);
42            chars.pop();
43        }
44    }
45}
leetcode/gen_parentheses.rs

leetcode/
gen_parentheses.rs
