4. Generate Parentheses

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

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

Approach

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        backtrack(ans,"",0,0,n);
        return ans;
    }
 
    void backtrack(List<String> ans, String curr, int open, int close, int max) {
        //2 times is the max bracket
        if (curr.length() == 2*max) {
            ans.add(curr);
            return;
        }
        //open bracket can only go upto half
        if (open < max)
            backtrack(ans, curr + '(', open + 1, close, max);
        //closing should not exceed opening
        if (close < open)
            backtrack(ans, curr + ')', open, close + 1, max);
    }
}