Dynamic programming solution, no recursive, no backtracking


  • 0
    S
    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector<vector<string>> lut(n+1);
            lut[0].push_back("");
            for (int i=1; i<=n; i++) {
                for (int j=0; j<i; j++) {
                    for (auto& inner:lut[j]) {
                        for (auto& outer:lut[i-1-j]) {
                            string s("(");
                            s += inner + ")" + outer;
                            lut[i].push_back(s);
                        }
                    }
                }
            }
            return lut[n];
        }
    };

  • 0
    B

    clever solution!


Log in to reply
 

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