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
Solutions
Solution 1: DFS + Pruning
The range of $n$ in the problem is $[1, 8]$, so we can directly solve this problem through "brute force search + pruning".
We design a function $dfs(l, r, t)$, where $l$ and $r$ represent the number of left and right brackets respectively, and $t$ represents the current bracket sequence. Then we can get the following recursive structure:
If $l \gt n$ or $r \gt n$ or $l \lt r$, then the current bracket combination $t$ is invalid, return directly;
If $l = n$ and $r = n$, then the current bracket combination $t$ is valid, add it to the answer array ans, and return directly;
We can choose to add a left bracket, and recursively execute dfs(l + 1, r, t + "(");
We can also choose to add a right bracket, and recursively execute dfs(l, r + 1, t + ")").
The time complexity is $O(2^{n\times 2} \times n)$, and the space complexity is $O(n)$.
implSolution{pubfngenerate_parenthesis(n:i32)->Vec<String>{letmutdp:Vec<Vec<String>>=vec![vec![];nasusize+1];// Initialize the dp vectordp[0].push(String::from(""));dp[1].push(String::from("()"));// Begin the actual dp processforiin2..=nasusize{forjin0..iasusize{letdp_c=dp.clone();letfirst_half=&dp_c[j];letsecond_half=&dp_c[i-j-1];forfinfirst_half{forsinsecond_half{letf_c=f.clone();letcur_str=f_c+"("+&*s+")";dp[i].push(cur_str);}}}}dp[nasusize].clone()}}