Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Input: n = 1
Output: ["()"]
1 <= n <= 8
Solutions (Click to expand)
Well-formed parentheses always begin with an opening ( and are complemented by a closing ) anywhere after in the array. There cannot be more than n opening brackets and at any point in the array there cannot be more closed brackets than opening brackets. We can create all possible valid combinations by backtracking to open parentheses and converting them to closing where ever possible by keeping count of all open and closed parentheses
- first start with building a string starting with all opening parentheses possible. (n)
"((("
- Add all its complementing closings.
"((((" + "))))"
- backtrack to the first opening parentheses and convert it to a closing. Keeping track of opening and closing parentheses convert the following to the appropriate opening and closing. General rule for backtracking the parentheses is to fill the rest of the string with as much opening and fill the rest wil closing
"((()""()))"
"((()" ")())"
"((()" "))()"
"(()" "(())"
"(()" "()())"
"(()" "())()"
"(()" ")(())"
- backtracking will repeat until the first opening parentheses. for every parentheses built, they will be added to the result string list.