My recursive and iterative cpp codes


  • 0
    C

    Recursive:

    class Solution {
    public:
        vector<string> generateParenthesis(int n) 
        {
            // [ '('generateParen(i)')'generateParen(n-i-1), for i in [n-1, 0] ]
            
            if(!n) return vector<string>(1, "");
            if(n == 1) return vector<string>(1, "()");
            
            vector<string> result;
            
            for(int i = n-1; i >=0; i--)
            {
                vector<string> inner = generateParenthesis(i);
                vector<string> outer = generateParenthesis(n-i-1);
                
                for(int i=0; i < inner.size(); i++)
                    for(int j=0; j < outer.size(); j++)
                        result.push_back( "(" + inner[i] + ")" + outer[j] );
            }
                
            return result;
        }
    };
    

    Iterative:

    class Solution {
    public:
        vector<string> generateParenthesis(int n) 
        {
            // [ '('generateParen(i)')'generateParen(n-i-1), for i in [n-1, 0] ]
            
            vector< vector<string> > result(n+1);
            result[0] = vector<string>(1, "");
            result[1] =  vector<string>(1, "()");
            
            for(int m = 2; m <= n; m++)
            {
                vector<string> res;
                
                for(int i = m-1; i >= 0; i--)
               {
                    vector<string>& inner = result[i];
                    vector<string>& outer = result[m-i-1];
                
                    for(int i=0; i < inner.size(); i++)
                        for(int j=0; j < outer.size(); j++)
                            res.push_back( "(" + inner[i] + ")" + outer[j] );
               }
               
               result[m] = res;
            }
                
            return result[n];
        }
    };

Log in to reply
 

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