C++ DP solution WITH explanations


  • 0
    U

    Basic idea: simple DP
    p[n] = Union_(i=1...n-1) {"(" + p[i] + ")" + p[n-1-i]}
    Time/space complexity is not very ideal but this problem cannot has strict restrictions on that (since the result set grows magnificently with input size)

    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector<vector<string>> ans(n+1);
            for (int i = 0; i <= n; i++) {
                if (i == 0) ans[i].push_back("");
                if (i == 1) ans[i].push_back("()");
                if (i > 1) {
                    for (int j = 0; j < i; j++) {
                        for (int k = 0; k < ans[j].size(); k++)
                        for (int l = 0; l < ans[i-1-j].size(); l++)
                            ans[i].push_back("(" + ans[j][k] + ")" + ans[i-1-j][l]);
                    }
                }
            }
            return ans[n];
        }
    };
    

Log in to reply
 

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