Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
[code lang="java"]
class Solution {
    public List<String> generateParenthesis(int n) {

    }
}
[code]

Idea – 1

If there is an open parenthesis left to take, we take it. If there is a close parenthesis left to take and taking it would not make close count bigger than open count, we take it. Time and space complexity both are proportional to Catalan number (exponential). 
[code lang="java"]
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        collect(n, 0, 0, "", ans);
        
        return ans;
    }
    
    private void collect(int n, int openused, int closeused, String current, List<String> result)
    {
        if(openused==n && closeused==n)
        {
            result.add(current);
            return;
        }
        
        if(openused < n)
        {
            collect(n, openused+1, closeused, current+"(", result);
        }
        
        if(closeused < openused)
        {
            collect(n, openused, closeused+1, current+")", result);
        }
    }
}
[code]

Runtime: 1 ms, faster than 96.17% of Java online submissions for Generate Parentheses.Memory Usage: 35.2 MB, less than 100.00% of Java online submissions for Generate Parentheses.

Leave a comment