题解 | #括号生成#

简单的递归回溯，思路简单清晰，一定看的懂得，如果感觉本解对你有益，请多多点赞题###

class Solution {
public:
//nol：temp中'('的数目， nor:temp中')'的数目
//temp中每多一个'(': sum++, 多一个 ')' :sum--;
//时刻保持sum >= 0, 即括号组合是合法的

string temp;
vector<string> re;
void dfs(int n, int nol, int nor, int sum) //递归的深度为2n,即有2n个位置需要填充
{
    if(nol > n || nor > n || sum < 0) //组合失败返回
    {
        return;
    }
    if(nol == n && nor == n && sum == 0) //组合成功返回
    {
        re.push_back(temp);
        return;
    }

    for(int i = 0; i < 2; i++) //每个位置有两种选择
    {
        if(i == 0)
        {
            temp += '(';
            dfs(n, nol+1, nor, sum+1);
        }
        if( i == 1)
        {
            temp += ')';
            dfs(n, nol, nor+1, sum-1);
        }

        temp = temp.substr(0, temp.size()-1); //回溯
    }
}


vector<string> generateParenthesis(int n) {
    // write code here

    dfs(n, 0,0,0);
    return re;
}

};