Generate Parentheses Problem

Problem Domain

Parenthesis problem has two variations:

1. Valid parentheses: stack solution
2. Generate parentheses: backtracking

Properties of a valid parentheses combination

• A valid parentheses combination has the same amount of left parentheses and right parentheses.
• For a valid parentheses combination $p$, the amount of left parentheses must be greater than or equal to the amount of right parentheses in every substring $p[0...i]$, where $0 <= i < len(p)$.

Generate Parentheses

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        // 0: left, 1: right
        int[] parenthesis = new int[2];
        StringBuilder path = new StringBuilder();

        backtrack(n, parenthesis, path, result);

        return result;
    }

    private void backtrack(int n, int[] parenthesis, StringBuilder path, List<String> result) {
        if (parenthesis[0] < parenthesis[1] || path.length() > 2 * n)
            return;

        if (parenthesis[0] == parenthesis[1] && parenthesis[0] == n) {
            result.add(path.toString());
            return;
        }

        parenthesis[0]++;
        path.append('(');
        backtrack(n, parenthesis, path, result);
        path.setLength(path.length() - 1);
        parenthesis[0]--;

        parenthesis[1]++;
        path.append(')');
        backtrack(n, parenthesis, path, result);
        path.setLength(path.length() - 1);
        parenthesis[1]--;
    }
}