22. Generate Parentheses

题目链接

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

解题思路

一道简单的dfs，结果花的时间还有点长才写好。

代码

class Solution {
public:
    void dfs(vector<string> &v, string cur, int li, int ri) {
        if (li <= 0 && ri <= 0) {
            v.push_back(cur);
            return;
        }

        if (li > 0) {//大于0，表明能放左括号
            dfs(v, cur + '(', li - 1, ri);
        }

        if (ri > li) {//可以放右括号
            dfs(v, cur + ")", li, ri - 1);
        }
    }

    vector<string> generateParenthesis(int n) {
        string left, right;
        for (int i = 0; i < n; ++i) {
            left += "(";
            right += ")";
        }
        vector<string> ans;
        dfs(ans, "(", n - 1, n);
        return ans;
    }

};