What is the complexity of my code, c++


  • 0
    R

    Hi, is this 2^n complexity? thanks

     class Solution {
        public:
            vector<string> generateParenthesis(int n) {
                vector<string> results;
                string result; 
                generateParenthesis(n, 0, 0, results, result);
                return results;
            }
        private:
            void generateParenthesis(int n, int left, int right, vector<string>& results, string result) {
                if((right+left) == 2*n && left == right) {
                    results.push_back(result);
                    return;
                }
                if(left+right == 2*n) return;
                if(left >= right) {
                    generateParenthesis(n, left+1, right, results, result+'(');
                }
                if(left > right) {
                    generateParenthesis(n, left, right+1, results, result+')');
                }
            }    
        };

  • 1
    L

    The total number of valid parentheses is a Catalan number,
    catalan number

    So time complexity should be O(C(2n,n)/(n+1)).
    Hope that helps:)


  • 0
    Z

    Great you solve my doubt


Log in to reply
 

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