22

class Solution {
public:
    vector<string> memo[10];
    vector<string> generateParenthesis(int n) {
        memo[1].push_back("()");
        memo[0].push_back("");
        return solve(n);
    }
    vector<string> solve(int n){
        if(memo[n].size()) return memo[n];
        for(int i=0; i<n; i++){
            for(string left: solve(i)){
                for(string right: solve(n-i-1)){
                    memo[n].push_back("("+left+")"+right);
                }
            }
        }
        return memo[n];
    }
};