description

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

 

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

 

Constraints:

  • 1 <= n <= 8

submission

impl Solution {
    // We solve this by dynamic programming, our intuition goes as follow
    // 0 => [ "" ]
    // 1 => [ "()" ]
    // ...
    // n => [ "(" + dp[i] + ")" + dp[n-i-1] for i in 0..n ]
    // Of course the real tranform equation here is way more complicate
    // but you get the idea, and why does this work?
    // There are two things to consider here: uniqueness and completeness
    // Why is every combination unique?
    // Because the combinations are unique at 0 and 1, and uniqueness
    // passes all the way down, when every combinations in dp[0..n]
    // are unique, the combinations in dp[n] are unique as well.
    // Why is this complete?
    // Because every valid combination can be written in the form of
    // < "(" + combo1 + ")" + combo2 >, when we allow combo to be empty.
    // With this method, we will collect all the combinations in this form,
    // so our answer is complete.
    pub fn generate_parenthesis(n: i32) -> Vec<String> {
        // case 0 and 1
        let mut dp = vec![vec![String::from("")], vec![String::from("()")]];
        // iterate through 2 => n
        for i in 2..=n {
            // dp...
            let mut ans = vec![];
            for j in 0..i {
                for l in &dp[j as usize] {
                    for r in &dp[(i - j - 1) as usize] {
                        ans.push(format!("({}){}", l, r));
                    }
                }
            }
            dp.push(ans);
        }
        // I don't have a good way to remove this clone
        dp[n as usize].clone()
    }
}