难 · 回溯

括号生成

你已经写过一回溯 —— 全排列 从 n 个值里选并撤销选择。这道只在两个字符之间选，但守着每个分支的两个计数器（open < n、close < open）干的正是当年 used[] 数组的剪枝活。

一句话答案对位置递归：<code>open &lt; n</code> 就放 <code>'('</code>，<code>close &lt; open</code> 就放 <code>')'</code>；到位置 2n 就打印。先试 '('，字典序白送。

题目

输入: 一个整数 n（1 ≤ n ≤ 8）。

输出: 全部 n 对括号的合法串，每行一个，顺序为「先试 '(' 后试 ')'」产生的顺序（即字典序）。

样例:

输入输出
2(())
()()
1()

n = 3 时，64 个原始组合里只有 5 个合法 —— 两条计数器规则把其余 59 个在「还没生成」时就扔掉了。这就是剪枝：在走进分支之前就拒绝它。

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 合法性就是两条局部规则

一个前缀能长成合法串，当且仅当：(1) 左括号用得少于 n；(2) 每个 ')' 都已被匹配 —— 每一步都归结为 close < open。两个整数计数器携带这两条事实；不需要栈、不需要最后再验一遍。规则边走边查，所以树会自我修剪。

提示 2 — 边界情况打印缓冲区

pos == 2 * n 时缓冲区是一整串 —— 而且由构造保证合法，因为计数器从没允许过别的。打印加换行，返回。注意全程没有任何「验证」步骤：正确性来自分支规则，而不是来自检查。

提示 3 — 两次尝试的顺序 = 输出顺序

函数内先试 '(' 再试 ')'。这个顺序的深度优先恰好按字典序访问所有串 —— 和 全排列 一样的免费午餐。把两个分支对调，输出的每一行都会重新排队。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int n;
char buf[20];

void generate(int pos, int open, int close) {
    if (pos == 2 * n) {
        for (int i = 0; i < pos; i++) cout << buf[i];
        cout << endl;
        return;
    }
    if (open < n) {
        buf[pos] = '(';
        generate(pos + 1, open + 1, close);
    }
    if (close < open) {
        buf[pos] = ')';
        generate(pos + 1, open, close + 1);
    }
}

int main() {
    cin >> n;
    generate(0, 0, 0);
    return 0;
}

这是「带回溯的搜索 + 剪枝」最纯粹的形态：原始搜索空间 2^(2n)，计数器把它剪到卡塔兰数 —— 约 4^n / n^1.5 —— 一条废枝都不走。这个家族在壮大：全排列 是「从集合里选」，本题是「带约束地选」。接下来的亲戚：带和条件的子集、N 皇后、数独。

深度解析

为什么这样做对

两个计数器编码了完整的合法性判断:左括号用得少于 n;右括号数永不超过左括号。在双重守卫下分支,搜索树的每个叶子都由构造保证合法 —— 无需事后验证,而且树在走进之前就被剪掉(2^(2n) 的原始串坍缩成卡塔兰数)。

代价

时间 O(卡塔兰(n) × n) —— 约 4^n / n^1.5 个串,每个 O(n) 打印 —— 递归深度 O(n)。n = 8 时是 1430 个串;若不剪枝、最后再验证,2^(2n) = 65536 个原始串都得试。

常见错法

  • 把 close < open 放宽成 close < n 会打印非法串 —— 这条守卫就是整个算法。
  • 忘了在 pos == 2n 打印(或在分支里打印)会得到半截前缀或重复串。
  • 先试 ')' 会重排输出;判题比对的是序列,所以尝试顺序和合法性同等重要。

下一步

同一副骨架,规则更丰富:全排列 是从集合里选,本题是在两个计数器下选。天然的下一站:带目标和的子集、N 皇后。

记住这两句

  • 剪枝 = 在走进分支之前拒绝它;这里两个计数器就够。
  • DFS 的尝试顺序定义输出顺序 —— '(' 在 ')' 前,字典序白送。
🐞 这段是错的 —— 点开,亲手让它挂一次

检查的是 close < n 而不是 close < open —— 非法串混了进来

#include <iostream>
using namespace std;

int n;
char buf[20];

void generate(int pos, int open, int close) {
    if (pos == 2 * n) {
        for (int i = 0; i < pos; i++) cout << buf[i];
        cout << endl;
        return;
    }
    if (open < n) {
        buf[pos] = '(';
        generate(pos + 1, open + 1, close);
    }
    if (close < n) {   // bug: should be close < open
        buf[pos] = ')';
        generate(pos + 1, open, close + 1);
    }
}

int main() {
    cin >> n;
    generate(0, 0, 0);
    return 0;
}