22. 括号生成

题目描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

分析

观察规律，构造结果。
n表示括号对数，
左边符号(,右边的符号),构造时：
当左边的符号数为n时，构造完成，直接补全右边的符号。
添加左边符号，递归生成余下的部分。
需要满足的条件，左边的符号数>右边的符号数。
添加右边符号，递归生成余下的部分。

代码

class Solution {
public:
    void doGenParenthesis(int n, string str, int left, int right, vector<string>& vec) {
        if(left == n) {
            vec.push_back(str.append(n - right, ')'));
            return;
        }
        doGenParenthesis(n, str + '(', left + 1, right, vec);
        if(left <= right)
            return;
        doGenParenthesis(n, str + ')', left, right + 1, vec);
    }
    
    vector<string> generateParenthesis(int n) {
        vector<string> vec;
        if(n <=0) {
            return vec;
        }
        doGenParenthesis(n, "", 0, 0, vec);
        return vec;
    }
};

题目链接

https://leetcode-cn.com/problems/generate-parentheses/description/