題目給定一個整數 n，代表有 n 對括號，請你回傳所有由 n 對括號組成的合法組合。合法的意思是，每個右括號 ) 都必須有對應的左括號 (，並且在字串中不能出現右括號比左括號先出現的情況。舉例來說，當 n = 3 時，合法的組合包含 "((()))", "(()())", "(())()", "()(())" 和 "()()()"，這些都是在括號配對上完全正確的排列方式。這類題目適合用回溯法來處理。我們會定義一個遞迴函數，負責一步一步建構字串。每次遞迴有兩種選擇：加入一個左括號 ( 或右括號 )。但我們不能亂加，必須遵守兩個規則：第一，如果左括號還沒用完（也就是目前已放的左括號數小於 n），就可以再放一個左括號；第二，右括號數必須小於左括號數，才能放右括號，這樣才能保證組合合法。當目前的字串長度達到 2 * n 時，代表一組完整的括號組合已經產生，可以加入結果清單。這樣透過不斷地嘗試與回溯，我們就能產生出所有合法的組合。
iThome鐵人賽
看影片追技術