22. 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

This problem asks us to list all possible combinations of parentheses, so we can use backtracking to solve it. While backtracking can find all combinations, some combinations are illegal. The following is a legal parenthesis combination.

Let’s look at an illegal parenthesis combination. Putting a closing parenthesis at the beginning makes it impossible to get a legal combination no matter how you put it later. According to this example, we can observe that when the remaining number of closing parenthesis is greater than or equal to the remaining number of opening parenthesis, we cannot put closing parenthesis.

Backtracking

• Time:
• Space:

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

    private void dfs(int left, int right, StringBuilder prefix, List<String> results) {
        if (left == 0 && right == 0) {
            results.add(prefix.toString());
        }

        if (left > 0) {
            prefix.append('(');
            dfs(left - 1, right, prefix, results);
            prefix.deleteCharAt(prefix.length() - 1);
        }

        if (right > left) {
            prefix.append(')');
            dfs(left, right - 1, prefix, results);
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }
}

Reference

• 22. Generate Parentheses, LeetCode.
• 22. Generate Parentheses, LeetCode Solutions.