[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<string> generateParenthesis(int n) {
        vector<string> result;
        if(n<1){
            return result;
        }
        
        getParenthesis(n, 0, 0, "", result);
        
        return result;
    }
    
    void getParenthesis(int n, int leftNumber, int rightNumber, string s, vector<string>& result){
        if(leftNumber==n&&rightNumber==n){
            result.push_back(s);
            return;
        }
        if(leftNumber<n){
            getParenthesis(n, leftNumber+1, rightNumber, s+"(", result);
        }
        if(rightNumber<leftNumber){
            getParenthesis(n, leftNumber, rightNumber+1, s+")", result);
        }
    }
};

[LeetCode] Generate Parentheses

原文：http://blog.csdn.net/kangrydotnet/article/details/45176557