HR:面试通过了，麻烦提供一下你过去12个月的银行流水和薪资证明，我们要走定薪流程。 这是HR压价的核武器

先说个日常场景吧：有天晚上我在工位上刷题，旁边小伙突然凑过来问我：“东哥，这个括号生成到底在考啥啊，看着就头大。” 其实这题一点都不玄乎，就是个标准的回溯模板题，用 Java 写起来也不长，但里面那一点“剪枝思维”，很多人刚开始容易拧不过来。

题目大概就是：给你一个整数 n，让你生成所有合法的括号组合，每个组合里有 n 个左括号 ( 和 n 个右括号 )。

比如：

• n = 1：只有 ()
• n = 2：()()、(())
• n = 3：((()))、(()())、(())()、()(())、()()()

“合法”两个字很关键，像 ())( 这种就不行，一路从左到右扫描时，任何时刻右括号都不能多于左括号。

如果不讲武德，最暴力的办法是：长度固定是 2 * n，每一位不是 ( 就是 )，所以一共 2^(2n) 种组合，把所有字符串列出来，再一个个检查是不是合法括号串，合法的留下，不合法扔掉。

问题：数量爆炸，而且检查本身也要时间，明显不适合在面试里这么写，对吧。

那我们就得换思路——与其先全都生成，再删掉一堆垃圾，不如一开始就只往“可能合法”的方向走，这就是回溯 + 剪枝的常见思路。

回溯核心就两个数字：left 和 right

你可以这样想：我们是从左到右、一位一位地“造”这个字符串的。造的过程中，我们只关心两件事：

1. 已经放了多少个左括号：left
2. 已经放了多少个右括号：right

最后目标：left == n && right == n，长度刚好 2 * n，而且中间过程一直合法。

那“合法”怎么体现在代码里呢？就两个约束条件：

• 左括号数量不能超过 n：left <= n
• 任意时刻，右括号不能比左括号多：right <= left

有了这俩条件，我们在递归里就只往“正确的方向”试探了，很多一看就不可能合法的串根本不会被生成出来，省了巨多时间。

上代码，Java 版长这样

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

publicclassGenerateParentheses{

public List<String> generateParenthesis(int n){
        List<String> res = new ArrayList<>();
if (n <= 0) {
return res;
        }
// 从空串开始回溯
        backtrack(res, new StringBuilder(), 0, 0, n);
return res;
    }

/**
     * @param res  最终结果列表
     * @param path 当前构建中的括号串
     * @param left 已经用了多少个左括号
     * @param right 已经用了多少个右括号
     * @param n    总共可以用的括号对数
     */
privatevoidbacktrack(List<String> res, StringBuilder path,
int left, int right, int n){

// 递归终止条件：左右括号都用满了
if (left == n && right == n) {
            res.add(path.toString());
return;
        }

// 还能放左括号，就尝试放一个左括号
if (left < n) {
            path.append('(');
            backtrack(res, path, left + 1, right, n);
// 回溯撤销刚才那一步
            path.deleteCharAt(path.length() - 1);
        }

// 只有当右括号数量小于左括号时，才能放右括号
if (right < left) {
            path.append(')');
            backtrack(res, path, left, right + 1, n);
// 回溯撤销
            path.deleteCharAt(path.length() - 1);
        }
    }

// 简单测一下
publicstaticvoidmain(String[] args){
        GenerateParentheses gp = new GenerateParentheses();
        System.out.println(gp.generateParenthesis(3));
    }
}

你可以把它当成“深度优先搜索 + 回溯”的模板题来记：

• 用 StringBuilder 或数组当“路径”
• 每次尝试一条分支，递归深入
• 回来的时候把刚刚那一步撤销掉（deleteCharAt 就是回溯）

用 n = 2 简单走一遍脑子就不乱了

n = 2 时，过程大概是这样：

1. 开始：""，left = 0, right = 0 只能先放左括号 → "("

2. "("，left = 1, right = 0

• 还能放左 → "(" + "(" = "(("
• 也可以放右 → "()"代码里是先走左，再回溯，再走右

最后你会得到两条路径：

• "((" -> "(())"
• "()" -> "()()"

中间没有一条是非法的，比如 ")(" 压根不会被构造出来，因为一旦 right > left 这种情况在代码里直接被挡住了。