C++ solution and explanation


  • 0
    H

    The solution is the same to construct all binary search trees given n nodes.

    if we got the solution from 0 to n, namely f(0), f(1),...f(n),
    f(n+1) = "(" + f(k) + ")" + f(n-k), 0 <= k <= n-1

    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            if(n == 0)
                return vector<string>();
            vector<vector<string> > solutions(n+1);
            solutions[0].push_back(string(""));
            solutions[1].push_back(string("()"));
            for(int i = 2; i <= n; ++i){
                for(int j = 0; j < i; ++j){
                    vector<string>& left = solutions[j];
                    vector<string>& right = solutions[i-j-1];
                    solute(solutions[i], left, right);
                }
            }
            return solutions[n];
        }
        void solute(vector<string>& result, const vector<string>& left, const vector<string>& right){
            string s = "(";
            for(int i = 0; i < left.size(); ++i){
                for(int j = 0; j < right.size(); ++j){
                    result.push_back(s+left[i]+")"+right[j]);
                }
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.