A simplified c++ DP solution, 4ms, 8 lines


  • 6
    R
    //dp[0] = ""
    //dp[i]='('+ dp[k]+')'+dp[i-1-k],k=0..i-i
    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector< vector<string> > dp(n+1, vector<string>());
            dp[0].push_back("");
            for(int i=1; i<=n; ++i){
                for(int k=0; k<i; ++k){
                    for(string s1: dp[k]){
                        for(string s2: dp[i-1-k])
                            dp[i].push_back("("+s1+")"+s2);
                    }
                }
            }
            return dp[n];
        }
    };

Log in to reply
 

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