括号生成算法详解：从面试尴尬聊到DFS回溯的解题思路

最近在网上看到一个挺有意思的讨论，说的是一位朋友在裁员三个月后去面试，当面试官问起他职业空窗期在做什么时，他坦诚地回答：“跑外卖，送了1278单，超时率0.3%，差评0条。我发现这比当主管收入高，还不用熬夜写PPT。” 结果对面的面试官和部门经理一下子都沉默了，场面变得相当微妙。

这件事让我琢磨了很久。问题的核心或许不在于“送外卖体不体面”，而在于两件事：第一，你在空窗期是否以一种积极、负责任的态度在生活和工作；第二，你是否敢于为自己的选择承担后果并清晰地表达其价值。能把外卖送到这种数据水平，本质上就是一种可量化的业绩，只不过工作场景从办公室换到了大街小巷。

换个角度看，面试本身也是一个双向筛选价值观的过程。能理解和欣赏这种独特经历的公司，往往更看重执行力、抗压能力和实际成果；而那些只在乎经历“听起来是否光鲜”的公司，早点在面试中暴露出来，对求职者而言未必是坏事，也算及时避坑了。

不过，吐槽归吐槽，技术人的老本行不能丢。 昨晚在地铁上，人挤人的，我单手扶着栏杆，另一只手刷手机看题，又碰到了那个老熟人——括号生成。脑子里瞬间拉响警报：这可是面试高频题啊！干脆趁热打铁，把思路和代码理清楚，下次再遇到就能脱口而出了。

题目理解与“合法”定义

题目要求很简单：给你一个数字 n，需要生成所有可能的、有效的括号组合，每个组合必须恰好包含 n 个左括号 ( 和 n 个右括号 )，并且排列顺序必须合法。

例如，当 n = 3 时，有效的组合为：

• "((()))"
• "(()())"
• "(())()"
• "()(())"
• "()()()"

那么，什么是“合法”的括号序列？记住两个核心条件就够了：

1. 最终数量相等：整个字符串中，左括号的数量必须等于右括号的数量，且都等于 n。
2. 前缀合法性：在从左到右扫描字符串的任何位置（即任何前缀），已出现的左括号数量都不能少于右括号数量。这确保了不会出现“先关门后开门”这种无效结构。

你可以想想 "())(" 这个序列，虽然左右括号总数最终都是2，但扫描到第二个字符时，右括号就比左括号多了，这显然是不合法的。

从暴力枚举到回溯剪枝

我当时的第一个念头是暴力法：生成所有长度为 2n 的、由 '(' 和 ')' 组成的字符串，然后逐个检查是否合法。但稍微一算就知道行不通：每一位有两种选择，总共有 2^(2n) 种可能，n 稍大一点这个数字就爆炸了，再加上遍历检查的开销，时间复杂度简直惨不忍睹，面试官可能直接让你回家等通知了。

正确的思路是“回溯”，或者说是深度优先搜索（DFS）配合剪枝。我们不是在所有可能性中大海捞针，而是在构造过程中就严格遵守规则，只走那些“可能合法”的路径，一旦发现当前路径走不下去了（即将非法），就立刻返回，尝试其他选择。

我们可以想象正在构造一个字符串 path，并时刻关注几个关键状态：

• n：需要生成的括号对总数（目标）。
• left：当前字符串中已经使用的左括号数量。
• right：当前字符串中已经使用的右括号数量。
• path：当前已经拼接出来的括号字符串。

在每一步，我们只有两种选择：

1. 添加左括号 (：只要 left < n，就说明左括号还没用完，可以添加。
2. 添加右括号 )：必须满足 right < left 才能添加。这个条件至关重要，它确保了在任何时刻，右括号的数量都不会超过左括号，从而满足了“前缀合法性”原则。

当 path 的长度达到 2 * n 时，说明我们已经放置了 n 对括号，并且由于构造过程的约束，它一定是合法的，这时就可以将其加入最终的结果列表。

这个过程很像走一个设计好的迷宫，每一步都先判断前方是不是墙（是否会导致非法），是墙就不走，不是墙才继续探索，这样能节省大量无用的搜索。

代码实现（Java）

下面是我整理后的 Java 实现，核心就是上面描述的DFS回溯过程：

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n < 0) {
            return res;
        }
        // 从空字符串开始，已使用的左右括号数均为0
        dfs(res, new StringBuilder(), n, 0, 0);
        return res;
    }

    /**
     * 深度优先搜索回溯函数
     * @param res   存放所有有效结果的列表
     * @param path  当前正在构造的字符串
     * @param n     需要生成的括号对总数
     * @param left  当前已使用的左括号数量
     * @param right 当前已使用的右括号数量
     */
    private void dfs(List<String> res,
                     StringBuilder path,
                     int n,
                     int left,
                     int right) {
        // 终止条件：路径长度达到 2*n，说明一对括号都放置完毕
        if (path.length() == 2 * n) {
            res.add(path.toString());
            return;
        }

        // 选择1：尝试添加左括号（如果还有名额）
        if (left < n) {
            path.append('(');
            dfs(res, path, n, left + 1, right);
            // 回溯：撤销刚才添加的左括号，尝试其他可能
            path.deleteCharAt(path.length() - 1);
        }

        // 选择2：尝试添加右括号（必须保证已添加的右括号少于左括号）
        if (right < left) {
            path.append(')');
            dfs(res, path, n, left, right + 1);
            // 回溯：撤销刚才添加的右括号
            path.deleteCharAt(path.length() - 1);
        }
    }

    // 测试一下
    public static void main(String[] args) {
        GenerateParentheses gp = new GenerateParentheses();
        System.out.println(gp.generateParenthesis(3));
        // 输出: [((())), (()()), (())(), ()(()), ()()()]
    }
}

递归过程推演（以 n=3 为例）

我们可以在脑海中模拟一下 n=3 时，其中一条路径的构造过程：

• 初始状态：path = "", left = 0, right = 0。
• 第一步：left < 3 成立，添加 ( → "("，left = 1。
• 第二步：left < 3 成立，添加 ( → "(("，left = 2。
• 第三步：left < 3 成立，添加 ( → "((("，left = 3。
• 第四步：此时 left < 3 不成立，不能再加左括号。检查 right < left (0 < 3) 成立，添加 ) → "((()"，right = 1。
• 后续步骤类似，根据规则继续添加右括号，最终形成 "((()))"，长度达到6，加入结果集。
• 然后，代码会通过deleteCharAt进行回溯，逐步退回之前的决策点，尝试不同的选择，例如退回到 "(()" 的状态，然后尝试生成 "(()())" 等其它合法组合。

正是因为我们在每一步都严格执行了 right < left 的剪枝条件，像 ")(" 这类明显非法的分支在递归树中根本不会被生成，从而极大地提升了算法效率。

最后聊聊

无论是应对一场突如其来的面试，还是解决一道经典的算法题，清晰的逻辑和坦诚的态度都是宝贵的。职业空窗期的经历，如果能被提炼成体现你韧性、执行力和责任感的故事，它就不是短板，而是一个独特的亮点。同样，面对算法题，理解其本质并运用像回溯这样高效的策略，远比死记硬背答案要可靠得多。

技术的世界很广阔，欢迎到云栈社区来分享你的见解或困惑，无论是关于职业发展的思考，还是对某道技术难题的钻研。