mediumStack

Generate Parentheses

Generate all correctly balanced strings made from n pairs of parentheses.

LeetCode ↗

Work through the cases

3 examples

Input notation

An integer n from 1 through 8.

Expected result

One string per line in lexicographic order.

Case 1

Input

Expected output

(())
()()

Case 2

Input

Expected output

()

Case 3

Input

Expected output

((()))
(()())
(())()
()(())
()()()

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

The first idea is to enumerate every string of length 2n and keep the valid ones. n ≤ 8 gives 2^{16} candidates, so it would pass, but most prefixes are already illegal. The bottleneck is generate-then-check: once a prefix has more ) than (, or either count exceeds n, no suffix can save it. A valid prefix only needs the two counts l and r: keep l ≥ r and neither above n. When l=r=n, record the string. DFS therefore tries appending ( or ) and prunes on those three inequalities. The search tree is much smaller than full enumeration; extra space is just the current string, O(n).

The range of n in the problem is [1, 8], so we can directly solve this problem through "brute force search + pruning".

We design a function dfs(l, r, t), where l and r represent the number of left and right brackets respectively, and t represents the current bracket sequence. Then we can get the following recursive structure:

- If l \gt n or r \gt n or l \lt r, then the current bracket combination t is invalid, return directly; - If l = n and r = n, then the current bracket combination t is valid, add it to the answer array ans, and return directly; - We can choose to add a left bracket, and recursively execute dfs(l + 1, r, t + "("); - We can also choose to add a right bracket, and recursively execute dfs(l, r + 1, t + ")").

The time complexity is O(2^{n × 2} × n), and the space complexity is O(n).

class Solution {
    private List<String> ans = new ArrayList<>();
    private int n;

    public List<String> generateParenthesis(int n) {
        this.n = n;
        dfs(0, 0, "");
        return ans;
    }

    private void dfs(int l, int r, String t) {
        if (l > n || r > n || l < r) {
            return;
        }
        if (l == n && r == n) {
            ans.add(t);
            return;
        }
        dfs(l + 1, r, t + "(");
        dfs(l, r + 1, t + ")");
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.