洛谷 P1706 全排列问题

// 洛谷 P1706 全排列问题 —— 第 ① 版：忘了把 used 改回去（**这一版是错的**）
//
// 输入：n（1 <= n <= 9）
// 输出：本该是 1..n 的全部排列，每个数占 5 个场宽
//
// 这份为什么存在：第 3 章的自测清单里点名了这个错 ——
// 「把 perm.cpp 里的 used[v] = false 删掉跑一次，说明白为什么会那样」。
// 这里把它真写出来，好让你看见那个「那样」到底长什么样。
//
// ⚠ 现象非常极端：**它只输出一行**（n >= 2 时）。
//    因为第一条路走到底之后，1..n 全被标成「用过了」，而**没有任何一个被还回来** ——
//    于是回到上一层想换个数时，一个能用的都找不到，整棵树当场枯死。
//
// ★ 这个错的可怕之处不在这道题（一眼就看出来），在别的题：
//   多数题目只输出一个**计数**或**最优值**，漏了撤销只会让答案**悄悄变小**，
//   不报错、不崩溃、样例还可能碰巧对。第 4 章 N 皇后那一章专门讲这件事。

#include <bits/stdc++.h>
using namespace std;

int n;
int pick[12];
bool used[12];

void dfs(int step) {
    if (step == n) {
        for (int i = 0; i < n; i++) printf("%5d", pick[i]);
        printf("\n");
        return;
    }
    for (int v = 1; v <= n; v++) {
        if (used[v]) continue;
        used[v] = true;                        // 进入
        pick[step] = v;
        dfs(step + 1);                         // 递归
        // ⚠ 这里少了一行 used[v] = false;
    }
}

int main() {
    if (!(cin >> n)) return 0;
    dfs(0);
    return 0;
}

// 洛谷 P1706 全排列问题 —— 第 ② 版：不用 used[]，每次回头找一遍（对，也能过）
//
// 输入：n
// 输出：1..n 的全部排列，字典序，每个数占 5 个场宽
//
// 这份为什么存在：想不起来「标记数组」这个套路的时候，人的自然反应是 ——
// **「我要放的这个数，前面用过了吗？回头翻一遍不就知道了。」**
//
//     for (int i = 0; i < step; i++) if (pick[i] == v) 用过了;
//
// ⇒ 这是对的，而且这道题 n <= 9，**它照样满分**。
//
// ★ 它和第 ③ 版的差别只有一处：判一次「用过没有」要花多少功夫。
//     这一版 O(n)（回头翻）    第 ③ 版 O(1)（查一个数组）
//   ⚠ 而这正是第 4 章 N 皇后那一章展开讲的东西 ——「打勾册子」这个套路。
//     那一章有一整节在讲：**冲突检查从「问所有人」变成「问那样东西」。**
//
// ⇒ 所以别觉得这一版「low」：想不起来标记数组时先写它，能过就是能过。

#include <bits/stdc++.h>
using namespace std;

int n;
int pick[12];

/** v 在 pick[0..step-1] 里出现过吗 */
bool taken(int step, int v) {
    for (int i = 0; i < step; i++) if (pick[i] == v) return true;
    return false;
}

void dfs(int step) {
    if (step == n) {
        for (int i = 0; i < n; i++) printf("%5d", pick[i]);
        printf("\n");
        return;
    }
    for (int v = 1; v <= n; v++) {
        if (taken(step, v)) continue;
        pick[step] = v;
        dfs(step + 1);
        // 不用撤销：taken() 只看 pick[0..step-1]，写在 pick[step] 上的痕迹没人读得到
    }
}

int main() {
    if (!(cin >> n)) return 0;
    dfs(0);
    return 0;
}

// 洛谷 P1706 全排列问题 —— 第 ③ 版：标记数组 + 进入/递归/撤销（正解）
//
// 输入：n（1 <= n <= 9）
// 输出：1..n 的全部排列，按字典序，**每个数占 5 个场宽**
//
// 这就是第 3 章 perm.cpp 那份代码，一个字都没变 —— 这道题是它的模板题。
// 三段式请练成肌肉记忆：
//
//     used[v] = true;    pick[step] = v;    // 进入
//     dfs(step + 1);                        // 递归
//     used[v] = false;                      // 撤销  <- 忘了这行见第 ① 版
//
// 为什么输出正好是字典序：内层循环 v 从 1 到 n 从小到大试，
// 于是每一层都先走小的那一支 ⇒ 出来就是字典序。**一行排序都没写。**
//
// ⚠ 和算法完全无关、但真会挂人的一条：题面写的是「每个数字保留 5 个场宽」，
//   所以是 printf("%5d", v)，不是空格分隔。见解析页第 ⑤ 步。

#include <bits/stdc++.h>
using namespace std;

int n;
int pick[12];
bool used[12];

void dfs(int step) {
    if (step == n) {
        for (int i = 0; i < n; i++) printf("%5d", pick[i]);
        printf("\n");
        return;
    }
    for (int v = 1; v <= n; v++) {
        if (used[v]) continue;
        used[v] = true;                        // 进入
        pick[step] = v;
        dfs(step + 1);                         // 递归
        used[v] = false;                       // 撤销
    }
}

int main() {
    if (!(cin >> n)) return 0;
    dfs(0);
    return 0;
}

// 洛谷 P1706 全排列问题 —— 第 ④ 版：标准库里本来就有（知道就行）
//
// 输入：n
// 输出：和第 ③ 版逐字节相同
//
// 这份为什么存在：C++ 标准库里有 next_permutation ——
// 它把当前排列变成**字典序里的下一个**，没有下一个就返回 false。
// 于是整道题变成一个 do-while。
//
// ★ 但请注意它的位置：**它是给你省时间的，不是给你替代理解的。**
//   · 考场上要「把所有排列列出来」，用它当然可以，写得快、不容易错；
//   · 可一旦题目变成「排列 + 剪枝」（第 4 章 N 皇后）、
//     「组合而不是排列」（P1157）、「边生成边判断」——
//     next_permutation 一概帮不上忙，因为**它不让你站在决策过程的中间**。
//
// ⇒ 所以顺序是：**先把第 ③ 版练到闭着眼睛能写，再把这一版当成一个顺手的工具。**
//   反过来的话，你会在第一道需要剪枝的题上原地卡住。
//
// ⚠ 用它之前数组必须**已经是字典序最小**（这里是 1,2,...,n），否则会漏掉前面那些。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = i + 1;          // 必须从字典序最小的那个开始

    do {
        for (int v : a) printf("%5d", v);
        printf("\n");
    } while (next_permutation(a.begin(), a.end()));

    return 0;
}