C++ Solution, using dp recursively, Maybe slow but easy to understand.


  • 0
    J
    class Solution {
    public:
        map<int, vector<string> > ans;
        vector<string> gen(int n) {
    	if (ans.find(n) != ans.end()) {
    	    return ans[n];
    	} else {
    	    vector<string> temp;
    	    map<string, bool> tempMap;
    	    if (n == 0) {
    	        temp.push_back(string(""));
    	    } else 
    	    if (n == 1) {
    		temp.push_back(string("()"));
    	    } else {
    		for (int i = 1; i < n; i++) {
    		    for (auto str1: gen(i)) {
    			for (auto str2: gen(n - i)) {
    			    tempMap[str1 + str2] = true;
    			}
    		    }
    		}
            for (auto str: gen(n - 1)) {
                tempMap["(" + str + ")"] = true;
            }
    		for (auto it = tempMap.begin(); it != tempMap.end(); ++it) {
    		    temp.push_back(it->first);
    		}
    	    }
    	    ans[n] = temp;
    	    return temp;
    	}
        }
        vector<string> generateParenthesis(int n) {
    	return gen(n);
        }
    };

Log in to reply
 

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