[Lc]22括号生成

题目

题解

1.递归法

class Solution {
    vector<string> res;//在私有变量定义res在存结果，
public:
    vector<string> generateParenthesis(int n) {//两种方法。1.递归
        if(n==0) return res;//特殊情况
        generateParenthesisDFS(n, n, "");//调用递归函数
        return res;
    }

    void generateParenthesisDFS(int left, int right, string out){
        if(left  > right) return;//若剩余左括号数量大于右括号，直接返回停止这一分支的递归
        if(left==0 && right==0) res.push_back(out);//若左右括号都用完，这一分支的字符加入结果中
        else{
            if(left > 0) generateParenthesisDFS(left-1, right, out+'(');
            if(right > 0) generateParenthesisDFS(left, right-1, out+')');
        }//调用递归，尝试加入左右括号
    }
};