[leetcode题解] 22.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:

[
  “((()))”,
  “(()())”,
  “(())()”,
  “()(())”,
  “()()()”
]

链接:https://leetcode-cn.com/problems/generate-parentheses

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

例如,给出 n = 3,生成结果为:

[
  “((()))”,
  “(()())”,
  “(())()”,
  “()(())”,
  “()()()”
]

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string s;
        
        dfs(res, s, n, n);
        return res;
    }
private:
    void dfs(vector<string> &res, string &s, int n_left, int n_right) {
        int i = 0;
        
        if (n_left == 0 && n_right == 0) {
            res.push_back(s);
            return;
        }
        
        if (n_left > 0) {
            s.push_back('(');
            dfs(res, s, n_left - 1, n_right);
            s.pop_back();
        }
        
        if (n_right > n_left) {
            s.push_back(')');
            dfs(res, s, n_left, n_right - 1);
            s.pop_back();
        }
    }
};

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解] 22.generate parentheses

本文链接地址:https://www.iaccepted.net/algorithm/leetcode/212.html

相关文章