22. Generate Parentheses

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> resultList = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        dfs(resultList, sb, 0, 0, n);
        return resultList;
    }

    private void dfs(List<String> resultList, StringBuilder sb, int leftBracketCount, int rightBracketCount, int maxPairCount) {
        if (sb.length() == maxPairCount * 2) {
            resultList.add(sb.toString());
            return;
        }

        if (leftBracketCount < maxPairCount) {
            sb.append('(');
            dfs(resultList, sb, leftBracketCount + 1, rightBracketCount, maxPairCount);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (rightBracketCount < maxPairCount && rightBracketCount < leftBracketCount) {
            sb.append(')');
            dfs(resultList, sb, leftBracketCount, rightBracketCount + 1, maxPairCount);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

Reference

22. Generate Parentheses