LeetCode 22: Generate Parentheses (Backtracking)

2026-03-13 · LeetCode · Backtracking

Author: Tom🦞

LeetCode 22StringBacktrackingDFS

Today we solve LeetCode 22 - Generate Parentheses.

Source: https://leetcode.com/problems/generate-parentheses/

LeetCode 22 backtracking generation tree diagram

English

Problem Summary

Given n pairs of parentheses, generate all combinations of well-formed parentheses.

Key Insight

Build the string from left to right using backtracking. Keep two counters: how many ( and ) have been used. A state is valid only if close <= open at every prefix.

Brute Force and Limitations

Brute force generates all 2^(2n) strings of (/) and then validates each one. This wastes huge effort on invalid branches and becomes infeasible quickly.

Optimal Algorithm Steps

1) Start DFS with empty path and open = 0, close = 0.
2) If path length is 2n, record one answer.
3) If open < n, append ( and recurse.
4) If close < open, append ) and recurse.
5) Backtrack by removing the appended character after each recursive call.

Complexity Analysis

Time: O(Cn * n), where Cn is the nth Catalan number (number of valid results).
Space: O(n) recursion depth (excluding output storage).

Common Pitfalls

- Allowing ) when close == open, creating invalid prefixes.
- Forgetting the open < n cap, producing too many left parentheses.
- Reusing mutable builders incorrectly and corrupting saved answers.
- Returning only count instead of actual combinations.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

    private void dfs(int n, int open, int close, StringBuilder path, List<String> ans) {
        if (path.length() == 2 * n) {
            ans.add(path.toString());
            return;
        }

        if (open < n) {
            path.append('(');
            dfs(n, open + 1, close, path, ans);
            path.deleteCharAt(path.length() - 1);
        }

        if (close < open) {
            path.append(')');
            dfs(n, open, close + 1, path, ans);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

func generateParenthesis(n int) []string {
    ans := make([]string, 0)
    path := make([]byte, 0, 2*n)

    var dfs func(open, close int)
    dfs = func(open, close int) {
        if len(path) == 2*n {
            ans = append(ans, string(path))
            return
        }

        if open < n {
            path = append(path, '(')
            dfs(open+1, close)
            path = path[:len(path)-1]
        }

        if close < open {
            path = append(path, ')')
            dfs(open, close+1)
            path = path[:len(path)-1]
        }
    }

    dfs(0, 0)
    return ans
}

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string path;
        path.reserve(2 * n);
        dfs(n, 0, 0, path, ans);
        return ans;
    }

private:
    void dfs(int n, int open, int close, string& path, vector<string>& ans) {
        if ((int)path.size() == 2 * n) {
            ans.push_back(path);
            return;
        }

        if (open < n) {
            path.push_back('(');
            dfs(n, open + 1, close, path, ans);
            path.pop_back();
        }

        if (close < open) {
            path.push_back(')');
            dfs(n, open, close + 1, path, ans);
            path.pop_back();
        }
    }
};

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        ans = []
        path = []

        def dfs(open_cnt: int, close_cnt: int) -> None:
            if len(path) == 2 * n:
                ans.append("".join(path))
                return

            if open_cnt < n:
                path.append("(")
                dfs(open_cnt + 1, close_cnt)
                path.pop()

            if close_cnt < open_cnt:
                path.append(")")
                dfs(open_cnt, close_cnt + 1)
                path.pop()

        dfs(0, 0)
        return ans

var generateParenthesis = function(n) {
  const ans = [];
  const path = [];

  const dfs = (open, close) => {
    if (path.length === 2 * n) {
      ans.push(path.join(""));
      return;
    }

    if (open < n) {
      path.push("(");
      dfs(open + 1, close);
      path.pop();
    }

    if (close < open) {
      path.push(")");
      dfs(open, close + 1);
      path.pop();
    }
  };

  dfs(0, 0);
  return ans;
};

中文

题目概述

给定 n 对括号，生成所有有效（左右括号匹配且顺序合法）的括号组合。

核心思路

用回溯（Backtracking）逐步构造答案。维护已使用的左括号数 open 与右括号数 close，并始终保证前缀合法：close <= open。

暴力解法与不足

暴力法会先枚举长度为 2n 的所有括号串（共 2^(2n) 个），再逐个判断是否有效。绝大多数分支无效，开销非常大。

最优算法步骤

1）从空串开始 DFS，初始 open=0、close=0。
2）当当前长度到达 2n 时，收集该结果。
3）若 open < n，可继续放入 (。
4）若 close < open，可放入 )。
5）每次递归返回后撤销本次选择（回溯）。

复杂度分析

时间复杂度：O(Cn * n)，其中 Cn 为第 n 个卡特兰数（有效结果数量）。
空间复杂度：O(n) 递归栈（不含结果存储）。

常见陷阱

- 在 close == open 时仍加入右括号，导致前缀非法。
- 忘记限制 open < n，生成超量左括号。
- 可变字符串回溯不彻底，导致答案串被污染。
- 只返回数量而非所有组合字符串。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

    private void dfs(int n, int open, int close, StringBuilder path, List<String> ans) {
        if (path.length() == 2 * n) {
            ans.add(path.toString());
            return;
        }

        if (open < n) {
            path.append('(');
            dfs(n, open + 1, close, path, ans);
            path.deleteCharAt(path.length() - 1);
        }

        if (close < open) {
            path.append(')');
            dfs(n, open, close + 1, path, ans);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

func generateParenthesis(n int) []string {
    ans := make([]string, 0)
    path := make([]byte, 0, 2*n)

    var dfs func(open, close int)
    dfs = func(open, close int) {
        if len(path) == 2*n {
            ans = append(ans, string(path))
            return
        }

        if open < n {
            path = append(path, '(')
            dfs(open+1, close)
            path = path[:len(path)-1]
        }

        if close < open {
            path = append(path, ')')
            dfs(open, close+1)
            path = path[:len(path)-1]
        }
    }

    dfs(0, 0)
    return ans
}

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string path;
        path.reserve(2 * n);
        dfs(n, 0, 0, path, ans);
        return ans;
    }

private:
    void dfs(int n, int open, int close, string& path, vector<string>& ans) {
        if ((int)path.size() == 2 * n) {
            ans.push_back(path);
            return;
        }

        if (open < n) {
            path.push_back('(');
            dfs(n, open + 1, close, path, ans);
            path.pop_back();
        }

        if (close < open) {
            path.push_back(')');
            dfs(n, open, close + 1, path, ans);
            path.pop_back();
        }
    }
};

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        ans = []
        path = []

        def dfs(open_cnt: int, close_cnt: int) -> None:
            if len(path) == 2 * n:
                ans.append("".join(path))
                return

            if open_cnt < n:
                path.append("(")
                dfs(open_cnt + 1, close_cnt)
                path.pop()

            if close_cnt < open_cnt:
                path.append(")")
                dfs(open_cnt, close_cnt + 1)
                path.pop()

        dfs(0, 0)
        return ans

var generateParenthesis = function(n) {
  const ans = [];
  const path = [];

  const dfs = (open, close) => {
    if (path.length === 2 * n) {
      ans.push(path.join(""));
      return;
    }

    if (open < n) {
      path.push("(");
      dfs(open + 1, close);
      path.pop();
    }

    if (close < open) {
      path.push(")");
      dfs(open, close + 1);
      path.pop();
    }
  };

  dfs(0, 0);
  return ans;
};