The most concise solution I know ever.


  • 6
    K
    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            if(n==0) return vector<string>(1,"") ;
            if(n==1) return vector<string>(1,"()") ;
            vector<string> result;
            for(int i=0;i!=n;i++)
                for(auto inner: generateParenthesis(i))
                    for(auto outter:  generateParenthesis(n-i-1))
                        result.push_back("("+inner+")"+outter);
            return result;
        }
    };
    

    I think this solution must be the most concise one. The idea is very clear.

    PS: The author is not me. Just share it with you.


  • 0
    S

    What is the time complexity? I cannot figure it out.


  • 0
    O

    The complexity is C_{2n}^n/(n+1), known as the Catalan number :-)


  • 0
    C

    This will be slow for large n because a lots of redundant computations for i < n in recursive call. DP would be much faster but space is costly.


  • 0
    T

    @opmiss That's the number of items in the result, does this include the recursion?


Log in to reply
 

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