22. Generate Parentheses Medium

1/**
2 * [22] Generate Parentheses
3 *
4 * Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
5 *  
6 * Example 1:
7 * Input: n = 3
8 * Output: ["((()))","(()())","(())()","()(())","()()()"]
9 * Example 2:
10 * Input: n = 1
11 * Output: ["()"]
12 *  
13 * Constraints:
14 * 
15 * 1 <= n <= 8
16 * 
17 */
18use std::collections::HashSet;
19pub struct Solution {}
20
21// problem: https://leetcode.com/problems/generate-parentheses/
22// discuss: https://leetcode.com/problems/generate-parentheses/discuss/?currentPage=1&orderBy=most_votes&query=
23
24// submission codes start here
25
26impl Solution {
27    pub fn generate_parenthesis(n: i32) -> Vec<String> {
28        let set = &mut HashSet::new();
29        Self::generate(&"".to_owned(), 0, 0, n, set);
30
31        set.iter().map(|x| x.to_owned()).collect()
32    }
33
34    fn generate(current: &String, open: i32, close: i32, n: i32, result: &mut HashSet<String>) {
35        if n == open && open == close {
36            result.insert(current.clone());
37            return
38        }
39
40        if open < n {
41            let mut c = current.clone();
42            c.push('(');
43            Self::generate(&c, open + 1, close, n, result);
44        }
45        if close < open {
46            let mut c = current.clone();
47            c.push(')');
48            Self::generate(&c, open, close + 1, n, result);
49        }
50
51    }
52}
53
54// submission codes end
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_22() {
62        println!("Got {:#?}", Solution::generate_parenthesis(3));
63    }
64}
65