难 · 递归

全排列

一个排列从一个选择开始：谁排第一？定下它，剩下的就是同样的问题缩小一号。递归把这句话直接写成代码 —— 选、委托、撤销选择。

一句话答案对位置递归：每个位置依次试没用过的值 v，放上、标记已用、递归下一层，然后撤销标记。按从小到大试值，输出的行自然就是字典序。

题目

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

输出: 1..n 的全部 n! 个排列，每行一个，数字间单个空格，按字典序。

样例:

输入输出
31 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

n ≤ 6 是因为 7! = 5040 行、10! = 360 万 —— 阶乘式增长正是本题要教的东西。递归深度只有 n，爆炸的是分支数。

你的解答

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

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

卡住了？提示

提示 1 — 先写边界情况

当 pos == n 时数组 perm 已满：按单个空格加换行打印，然后 return。每个递归都需要一个停止下探的最小情形 —— 先把它写出来，函数才有立足点。

提示 2 — 这个循环本身就是分支

在位置 pos，让 value 从 1 到 n 循环。跳过 used 里已标记的；否则：perm[pos] = value; used[value] = 1; generate(pos + 1); —— 然后是新手最容易忘的一步：used[value] = 0; 把这个值还回去。按从小到大试值，字典序就白送了。

提示 3 — 信任递归

在 pos 放好一个值之后，generate(pos + 1) 必须按序产生当前前缀的所有补全，然后返回。别用手一层层往下追 —— 证明是结构性的：这就是同一个问题的更小实例。

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

int n;
int used[10];
int perm[10];

void generate(int pos) {
    if (pos == n) {
        for (int i = 0; i < n; i++) {
            cout << perm[i];
            if (i < n - 1) cout << " ";
        }
        cout << endl;
        return;
    }
    for (int value = 1; value <= n; value++) {
        if (used[value]) continue;
        used[value] = 1;
        perm[pos] = value;
        generate(pos + 1);
        used[value] = 0;
    }
}

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

你已经写出了第一个回溯：选、递归、撤销。同一副骨架能解子集、N 皇后、数独和迷宫路径 —— 变的只是循环体。想从另一面看递归（调用栈而不是搜索树），去爬 汉诺塔。

深度解析

为什么这样做对

搜索空间是一棵树：深度是位置，分支是没用过的值。回溯按字典序的 DFS 顺序走完这棵树，「撤销标记」这一步让一个值还能出现在别的分支里 —— 没有它，每个值在整个运行里只能用一次。

代价

时间 O(n! × n) —— n! 行，每行打印 O(n) —— 递归栈和数组占 O(n) 空间。n = 10 时已经是 3600 万行：阶乘增长跑赢一切优化。

常见错法

  • 递归调用之后忘了 used[value] = 0;。n = 2 时输出一行而不是两行；n = 6 时几行而不是 720 行 —— 而原因只是一行代码的缺失。
  • 在循环里打印而不是在 pos == n 打印。你会把每个前缀都打出来，行数和 n! 再也对不上。

下一步

同一副骨架，不同的载荷：子集、N 皇后、迷宫。递归的「调用栈视角」主角是 汉诺塔。

记住这两句

  • 回溯 = 选、递归、撤销；「撤销」不是可选项。
  • 按从小到大试值，字典序就白送。
🐞 这段是错的 —— 点开,亲手让它挂一次

从来不把值还回去 —— 少了 used[value] = 0

#include <iostream>
using namespace std;

int n;
int used[10];
int perm[10];

void generate(int pos) {
    if (pos == n) {
        for (int i = 0; i < n; i++) {
            cout << perm[i];
            if (i < n - 1) cout << " ";
        }
        cout << endl;
        return;
    }
    for (int value = 1; value <= n; value++) {
        if (used[value]) continue;
        used[value] = 1;
        perm[pos] = value;
        generate(pos + 1);
    }
}

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