0022 - Generate Parentheses

0022 - Generate Parentheses

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

Examples

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

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

Constraints

• 1 <= n <= 8

Java Solution (Backtracking)

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if (n < 0) {
            return result;
        }
        backtrack(result, n, n, new StringBuilder());
        return result;
    }
    
    private void backtrack(List<String> result, int open, int close, StringBuilder sb) {
        if (open == 0 && close == 0) {
            result.add(sb.toString());
            return;
        }

        if (open > 0) {
            sb.append("(");
            backtrack(result, open - 1, close, sb);
            sb.setLength(sb.length() - 1);
        }
        if (open < close) {
            sb.append(")");
            backtrack(result, open, close - 1, sb);
            sb.setLength(sb.length() - 1);
        }
    }
}