|
| 1 | +/** |
| 2 | +Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. |
| 3 | +
|
| 4 | +For example, given n = 3, a solution set is: |
| 5 | +
|
| 6 | +"((()))", "(()())", "(())()", "()(())", "()()()" |
| 7 | +
|
| 8 | +
|
| 9 | +Solution: |
| 10 | +This is a very classic Recursion and Dynamic Programming Problem. |
| 11 | +We can use a recursive DFS method to solve this problem. |
| 12 | +
|
| 13 | +Idea: |
| 14 | +we can build all the valid strings from scratch. That is, we build all |
| 15 | +strings by inserting left paren and right paren one by one. |
| 16 | +
|
| 17 | +Note three things: |
| 18 | +1, the length of a valid string must be 2n, n is the number of left paren |
| 19 | +and right paren we can use. |
| 20 | +2, In each position of the string, we have two options: insert a left paren |
| 21 | +or insert a right paren as long as the string stays valid. |
| 22 | +3, In all substrings of a valid string, the number of right paren cannot be |
| 23 | +more than the number of left paren. |
| 24 | +
|
| 25 | +So each time in the recursive method, we will insert a left paren and a right |
| 26 | +paren as long as the string is valid then continue the recursive call to finally |
| 27 | +build all valid strings. |
| 28 | +
|
| 29 | +Then we need to know when we can insert a left paren and when we can insert a right |
| 30 | +paren? That's the key point to solve this problem and reduce unnecessary recursive calls. |
| 31 | +1, Left Paren: As long as we haven't used up all left parentheses, we can always insert |
| 32 | +a left paren. |
| 33 | +2, Right Paren: If the current number of right paren is less than left paren, we can insert |
| 34 | +a right paren. Since in any substring of a valid string the number of right paren must be no |
| 35 | +more than left paren. If currently the number of right paren is equal to left paren, we cannot |
| 36 | +insert a right paren. Because it will lead an invalid substring. |
| 37 | +In other words, if after inserting a right paren, right parens are not more than left parens, |
| 38 | +then we can insert a right paren. |
| 39 | +
|
| 40 | +Know the above information, we can easily come up with the following method: |
| 41 | +In the recursive method, we need to know the total number n, current number of left and right paren, |
| 42 | +current string and the result List of strings. |
| 43 | +
|
| 44 | +Base case: current number of left and right paren are both n, then we already got a valid string. We |
| 45 | +just need to put the string into List and return. |
| 46 | +
|
| 47 | +Otherwise, we insert left and right paren to the current string recursivelly if the string will stay |
| 48 | +valid. If number of left paren is less than n, we can insert left paren. If number of right paren |
| 49 | +is less than left paren, we can insert right paren. |
| 50 | +
|
| 51 | +Time complexity: O(n^2) |
| 52 | +*/ |
| 53 | + |
| 54 | +//Recursive DFS solution |
| 55 | +public class Solution { |
| 56 | + public IList<string> GenerateParenthesis(int n) { |
| 57 | + IList<string> result = new List<string>(); |
| 58 | + string s=""; |
| 59 | + DFS(n, 0, 0, s, result); |
| 60 | + return result; |
| 61 | + } |
| 62 | + //Recursive DFS method to add '(' and ')' to s |
| 63 | + private void DFS(int n, int leftNum, int rightNum, string s, IList<string> result){ |
| 64 | + if(leftNum == rightNum && leftNum==n){ |
| 65 | + result.Add(s); |
| 66 | + return; |
| 67 | + } |
| 68 | + if(leftNum<n) |
| 69 | + DFS(n,leftNum+1, rightNum, s+"(", result); |
| 70 | + if(rightNum<leftNum) |
| 71 | + DFS(n,leftNum, rightNum+1, s+")", result); |
| 72 | + } |
| 73 | +} |
| 74 | + |
| 75 | + |
0 commit comments