[LeetCode] 22. Generate Parentheses

轉自LeetCode

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

<Solution>

這題也是要求排列組合，直覺就用 DFS => 先求解，再回頭考慮其他情況

那 DFS 通常會用 recursive 的解法

判斷條件有

• 當左括號數目和右括號數目都為 0的時候，目前的字串是一組答案

• 只要左括號數目還不等於 0，就先處理左括號

• 右括號數目不等於 0，且還多於左括號數目 (不然會發生 ")(" 這種狀況)，處理右括號

code 如下


kotlin