Dfs + Memory search. (8ms)


  • 0
    L

    Algo: dfs + memory search

       class Solution {
        public:
            vector<string> generateParenthesis(int n) {
        		vector<string> ans;
        		if (n == 0)
        			return move(ans);
        		if (n == 1) {
        			ans.push_back("()");
        			return move(ans);
        		}
        		if (dic.find(n) != dic.end())
        			return dic[n];
        
        		for (int i = 1; i <= n; ++i) {
        			auto left = generateParenthesis(i - 1);
        			if (left.empty())
        				left.push_back("");
        
        			auto right = generateParenthesis(n - i);
        			if (right.empty())
        				right.push_back("");
        
        			for (auto & x : left) {
        				for (auto & y : right) {
        					ans.push_back("(" + x + ")" + y);
        				}
        			}
        		}
        		return dic[n] = move(ans);
            }
        	unordered_map<int, vector<string> > dic;
        };

Log in to reply
 

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