Here is my accepted solution.


  • 2
    F

    I planned to use dp here, because generateParenthesis2( 2) , generateParenthesis2( 3 ) and etc are calculated multiple times. Given that more space is needed for dp and this one has been accepted, I didn't solve the problem in dp way.

    // This problem can be treated in the same way as getting all of B-trees with n nodes. 
    
    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector<string> result;
            
            set<string> resultset = generateParenthesis2( n );
            
            result.insert( result.end(), resultset.begin(), resultset.end() );
            
            return result;       
        }
    
    private:
        set<string> generateParenthesis2( int n ) // use "set" to remove the duplicates of one string. 
        {
            set<string> resultset;  
            
            if( 0 == n )
            {
                return resultset;
            }
            
            if( n == 1)
            {
                resultset.insert( string("()"));
                return resultset;
            }
            
            for( int i = 1; i <= n /2; i++ ) 
            {
                vector<string> left = generateParenthesis( i );
                vector<string> right = generateParenthesis( n - i );
                
                for( vector<string>::iterator tleft = left.begin(); tleft != left.end(); tleft++ )
                {
                    for(vector<string>::iterator tright = right.begin(); tright != right.end(); tright++ )
                    {
                        resultset.insert( *tleft + *tright );
                        
                        resultset.insert( *tright + *tleft );
                    }
                }
                
                
                if( 1 == i ) // special case: root parenthesis contains all the other parenthesises.
                {
                    for(vector<string>::iterator tright = right.begin(); tright != right.end(); tright++ )
                    {
                        resultset.insert( "(" + *tright + ")" );
                    }
                }
            }
            
            return resultset;
        }
    
    };

  • 0
    K

    I used set and it says memory out of limit.


Log in to reply
 

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