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給定一個正整數 n
要求實作一個演算法 算出所所有由 n 組字元配對 ‘(’, ‘)’ 所組成的合法配對字元
假設有一個字串 s 是合法的字元配對
1 代表 s 具有 n 組字元配對 ‘(’, ‘)’ 所組成, 所以字串 s 具有 2*n 個字元
2 因為每個 ‘(’ 必須找到對應在其右方的 ‘)’, 所以要能配對完成, 必須符合以下條件
2.1 從字串左方往右逐步計算 ‘(’ 與 ‘)’ 個數，會發現每個位置 ‘(’ 個數 ≥ ‘)’ 個數
當 ‘)’ 個數大於 ‘(’ 如下圖
所以我們可以使用 backTracking 的方式逐步找出所有可能的字串