タイトル:

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:

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

テーマ：

1つの数字nを与えて、括弧の対数を代表して、n対括弧のマッチングのすべての情況を求めます.

考え方:

　　
問題を手に入れた最初の反応は、この問題が典型的な再帰であることを考えたが、長い間経ってもどのように再帰するか分からない.先輩のブログを参考に:http://blog.csdn.net/wwh578867817/article/details/46392701、法則左半カッコは、右半カッコ以上であることが得られる.

コード1:

class Solution {
public:
    std::vector<std::string> generateParenthesis(int n) {
        std::vector<std::string> result;
        
        if (n <= 0) {
            return result;
        }
        std::string s;
        addBrackets(n, n, s, result);
        
        return result;
    }
    
private:
    void addBrackets(int left, int right, std::string s, std::vector<std::string> &result)
    {
        if (left == 0 && right == 0) {
            result.push_back(s);
            return;
        }
        
        if (left == right) {
            addBrackets(left - 1, right, s + "(", result);
        } else {
            if (left > 0) {
                addBrackets(left - 1, right, s + "(", result);
            }
            if (right > 0) {
                addBrackets(left, right - 1, s + ")", result);
            }
        }
    }
};

コード2:

class Solution {
public:
    
    //                      
    std::vector<std::string> generateParenthesis(int n) {
        std::string s;
        std::vector<std::string> result;
        generate(n, n, s, result);
        return result;
    }

    void generate(int left, int right, std::string s, std::vector<std::string> &result){
        if(left){
            generate(left - 1, right, s + "(", result); //                  
            if(left != right){    //       
                generate(left, right - 1, s + ")", result);    //     
            }
        }else{
            if(right){   //                        
                result.push_back(s + std::string(right,')'));
            }
        }
        return;
    }
};