括号生成 shuitang

题目

22. 括号生成

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例:

输入:n = 3
输出:[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

解法

这题貌似见过很多次了,我一直使用之前的思路,是采用递归思路来写,到今天才发现之前的思路不对啊……害,还是老老实实使用回溯法来做,代码如下:(吐槽一个 C++ 的字符串处理)

class Solution {
public:
    void dfs(vector<string>& ans, int n, string cur){
        if(cur.length() == 2*n){
            ans.push_back(cur);
            return;
        } 
        string temp = cur;
        temp.push_back('(');
        int sum = 0;
        for(int i=0;i<temp.length();++i){
            if(temp[i] == '(') sum++;
        }
        if(sum <= n) dfs(ans,n,temp);

        temp[temp.length()-1] = ')';
        sum = 0;
        for(int i=0;i<temp.length();++i){
            if(temp[i] == '(') sum++;
            else sum--;
        }
        if(sum >= 0) dfs(ans,n,temp);
    }
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string t;
        dfs(ans,n,t);
        return ans;
    }
    
};