题解 | #括号生成#

回溯法，其实就是i<j 和 i>=j这两个在回溯，其他那几个都是为了完成剩余的任务。

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> generateParenthesis(int n) {
        // write code here
        vector<string> result;


        string s="";// 保存括号,每次的括号组
        parenthesis(result,n,n,s);

        return result;
    }

    void parenthesis(vector<string>& result,int i, int j, string s){
         //第一种：当n为0时，也就是i = j = 0，这时，说明不需要分配括号，直接返回字符串类型即可。
        if(i==0&&j==0){
            result.push_back(s);
            return;
        }

        if(i==0&&j>0){
            parenthesis(result,i,j-1,s+")");

        }else if(j==0&&i>0){
            parenthesis(result,i-1,j,s+"(");

        }else if(i<j){
            parenthesis(result,i-1,j,s+"(");
            parenthesis(result,i,j-1,s+")");

        }else if(i>=j){
            parenthesis(result,i-1,j,s+"(");

        }
    }
};