Leetcode22：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:

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

分析

这道题比较容易想到的就是用递归DFS来求解。使用两个参数分别表示左括号和右括号的剩余数量，递归的终止条件是右括号的剩余数量小于左括号的剩余数量，只有这样才会产生括号不匹配的情况。其他情况就使结果字符串加上左括号或者右括号，并使相应的括号数量减一，继续递归。直到所有括号都使用完，这时将字符串保存在结果中。

AC代码如下：

class Solution {
    
public:vector<string> generateParenthesis(int n) {
    vector<string> result;dfs(n, n, "", result);return result;}int dfs(int ln, int rn, string s, vector<string>& result){
    if(ln > rn)//括号不匹配的情况{
    return 0;}if(ln == 0 && rn == 0)//递归结束，保存结果{
    result.push_back(s);}if(ln > 0)//左括号{
    dfs(ln-1, rn, s+'(', result);}if(rn > 0)//右括号{
    dfs(ln, rn-1, s+')', result);}return 0;}
};