Generate Parentheses

Problem

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

Solution

Backtracking is actually super fun.

class Solution {
    public List<String> generateParenthesis(int n) {
        var answers = new ArrayList<String>();
        solve(n, 0, "", answers);
        return answers;
    }

    public void solve(int n, int depth, String current, List<String> answers) {
        // at each point, we can choose to nest or not.
        if (n == 0) {
            // close out this depth
            for (int i = 0; i < depth; i++) {
                current = current + ")";
            }

            answers.add(current);
            return;
        }

        // nest
        solve(n - 1, depth + 1, current + "(", answers);

        // close out
        for (int i = 1; i < depth + 1; i++) {
            current = current + ")";
            solve(n - 1, depth - i + 1, current + "(", answers);
        }
    }
}