[LeetCode] Generate Parentheses

[LeetCode] Generate Parentheses

Generate Parentheses

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

解題思路：

我第一感覺就是回溯，通過遞歸實現。但是遞歸的條件遲遲沒有想出。可以這麼做，分別記錄當前字符串的（和）個數，若（個數小於n，當前字符串加上（，遞歸調用下一層。若）小於（的個數，當前字符加上），遞歸調用下一層。若（和）的數目都等於n，停止遞歸調用，將s加入結果集。代碼如下：

class Solution {
public:
    vector generateParenthesis(int n) {
        vector result;
        if(n<1){
            return result;
        }
        
        getParenthesis(n, 0, 0, "", result);
        
        return result;
    }
    
    void getParenthesis(int n, int leftNumber, int rightNumber, string s, vector& result){
        if(leftNumber==n&&rightNumber==n){
            result.push_back(s);
            return;
        }
        if(leftNumber