problem

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

// 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.
impl Solution {
    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 _ in 2..=n {
            // dp...
            let mut ans = vec![];
            let mut forward = dp.iter();
            let mut backword = dp.iter().rev();
            while let Some((left, right)) =
                forward.next().zip(backword.next())
            {
                for l in left {
                    for r in right {
                        ans.push(format!("({}){}", l, r));
                    }
                }
            }
            dp.push(ans);
        }
        dp.pop().unwrap_or_default()
    }
}