括号生成+力扣

题目

题目链接

. - 力扣（LeetCode）

题目描述

代码实现

class Solution {
    int left, right;
    vector<string> ret;
    string path;
public:
    vector<string> generateParenthesis(int n) {
        dfs(n);
        return ret;
    }
    void dfs(int n){
        if(right == n){
            ret.push_back(path);
            return;
        }
        if(left < n){
            path.push_back('(');
            left++;
            dfs(n);
            path.pop_back();
            left--;
        }
        if(right < left){
            path.push_back(')');
            right++;
            dfs(n);
            path.pop_back();
            right--;
        }
    }
};

思路分析

1、有效符号，需要左括号 = 右括号

2、从头开始的任意一个子串的左括号需要>=右括号。

3、再说剪枝，左括号的数量不能超过n。右括号数量少于左括号。只有这两种情况才能继续添加左括号或者右括号的。

4、递归出口就是右括号数量等于n的时候。

下边是决策图的示意图，可供参考