Problem :

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: ["()"]

核心思維 :

1. 設定result儲存結果，並列出當前字串和可用得的左右括號數量
2. 進行遞迴

• 若沒有左和右括號，將當前的括號組合放入結果中
• 若有左括號，則新增 ’ ( ’ 進行遞迴，並進行回溯
• 若右括號的數量大於左括號的數量，則新增'('進行遞迴，並進行回溯

3. 回傳結果

程式碼 :

class Solution {
public:
    void solve(vector<string>& result, string output, int left, int right)
    {
        //若沒有左和右括號，將當前的括號組合放入結果中
        if(left == 0 and right == 0){
            result.push_back(output);
            return;
        }
        //若有左括號，則新增'('進行遞迴
        if(left > 0){
            output.push_back('(');
            solve(result,output,left-1,right);
            //回溯，移除最後一個字符進行其他配對
            output.pop_back();
        }
        //若右括號的數量大於左括號的數量，則新增'('進行遞迴
        if(right > left){
            output.push_back(')');
            solve(result,output,left,right-1);
            //回溯，移除最後一個字符進行其他配對
            output.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        //設定result儲存所有組合結果，並列出當前字串
        vector<string> result;
        string output;
        //左和右括號的數量
        int left = n;
        int right = n;
        //進行遞迴
        solve(result,output,left,right);
        //回傳結果
        return result;
    }
};

結論 :

這題的題目是找出題目給予的括號數量可以排列的所有組合，利用遞迴的方式持續進行配對，直到找出所有組合，相比前面堆疊遇到的括號配對問題，回溯的利用遞迴的方式依序配對，方法較為直觀且簡易明瞭，適用於這種較小規模的問題。