Recursive solution with explanation adding "()" not separately


  • 0
    A

    There is a trick here, that we can still add "()" together, but skip left & right check with backtrack.
    If we follow the logic by adding "()" to each place of the string we will have duplicates, but we can start from the latest position in our recursive call:

    void solve(vector<string> &res, string s, int n, int k)
    {
    	if (s.length() == n)
    	{
    		res.push_back(s);
    		return;
    	}
    	for (int i = k; i <= s.length(); i++)
    		solve(res, s.substr(0, i) + "()" + s.substr(i, s.length() - i), n, i+1);
    }
    
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        solve(res, "", n*2, 0);
        return res;
    }

Log in to reply
 

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