LeetCode-in-Scala.github.io
22. Generate Parentheses
Medium
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
Solution
import scala.collection.mutable.ListBuffer
object Solution {
def generateParenthesis(n: Int): List[String] = {
val sb = new StringBuilder()
val ans = ListBuffer[String]()
generate(sb, ans, n, n).toList
}
private def generate(sb: StringBuilder, str: ListBuffer[String], open: Int, close: Int): ListBuffer[String] = {
if (open == 0 && close == 0) {
str += sb.toString()
return str
}
if (open > 0) {
sb.append('(')
generate(sb, str, open - 1, close)
sb.deleteCharAt(sb.length - 1)
}
if (close > 0 && open < close) {
sb.append(')')
generate(sb, str, open, close - 1)
sb.deleteCharAt(sb.length - 1)
}
str
}
}