洛谷 P1157 组合的输出

// 洛谷 P1157 组合的输出 —— 第 ① 版：把第 3 章的全排列改一改（**这一版是错的**）
//
// 输入：n r（1 < r <= n < 21）
// 输出：本该是所有组合，实际是所有**排列**
//
// 这份为什么存在：它是几乎所有人的第一反应，所以它必须被写出来、被跑一遍、被看见错在哪。
// 「教科书直接给标准答案」的毛病就在这儿 —— 跳过这一步，学生不知道自己为什么会走错。
//
// 改动只有一处：第 3 章 perm.cpp 的出口是 `if (step == n)`，这里改成 `if (step == r)`。
// 看起来完全合理：本来选 n 个，现在只选 r 个。
//
// ⚠ 但它给出的是 A(n, r) 行，不是 C(n, r) 行。n = 5、r = 3 时它输出 60 行，而答案只有 10 行。
//    因为「1 2 3」和「2 1 3」在它眼里是两回事 —— 排列关心顺序，组合不关心。
//    ⇒ 这一版错在**题意**上，不在代码上。代码写得一点毛病都没有。

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

int n, r;
int pick[25];        // pick[0..step-1] = 已经选好的数
bool used[25];

void dfs(int step) {
    if (step == r) {                                   // ← 唯一改动：n 换成 r
        for (int i = 0; i < r; i++) printf("%3d", 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 >> r)) return 0;
    if (r < 0 || r > n) return 0;
    dfs(0);
    return 0;
}

// 洛谷 P1157 组合的输出 —— 第 ② 版：排列 + 排序 + set 去重（**对，但跑不完**）
//
// 输入：n r
// 输出：所有组合，字典序（set<vector<int>> 天然就是字典序）
//
// 这份为什么存在：发现第 ① 版把「1 2 3」和「2 1 3」当成两个之后，
// 最自然的补救就是「排个序，重复的扔掉」。**这个想法是对的，答案也是对的。**
//
// ⚠ 但它治的是症状不是病根：那 A(n, r) 条排列**照样一条不落地生成了**，
//    只是最后被丢进 set 里合并掉。n = 20、r = 10 时 A(20,10) = 670 442 572 800 ——
//    六千七百亿次递归，而正确答案只有 C(20,10) = 184 756 行。
//    ⇒ **多算的倍数正好是 r! = 10! = 3 628 800** —— 每个组合的 r! 种排列各被数了一遍。
//    （A(n,r) / C(n,r) = r!，这不是巧合，就是组合数的定义。）
//
// ★ 这一版最值钱的一课：**「答案对」和「能过」是两件事。**
//    小数据（比如样例的 n=5 r=3）它跑得飞快，一交上去就是 TLE。
//    ⇒ 提交前先拿题面给的上界估一估工作量，这一步只要三秒钟。

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

int n, r;
int pick[25];
bool used[25];
set<vector<int>> seen;      // 排好序的组合，set 自动去重、自动字典序

void dfs(int step) {
    if (step == r) {
        vector<int> comb(pick, pick + r);
        sort(comb.begin(), comb.end());               // ← 补救：先排序，顺序就不算数了
        seen.insert(comb);                            // ← 再去重
        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 >> r)) return 0;
    if (r < 0 || r > n) return 0;
    dfs(0);
    for (const vector<int>& comb : seen) {
        for (int v : comb) printf("%3d", v);
        printf("\n");
    }
    return 0;
}

// 洛谷 P1157 组合的输出 —— 第 ③ 版：换成第 3 章那棵**子集树**（★ 这一版就能 AC）
//
// 输入：n r
// 输出：所有组合，字典序
//
// 这份为什么存在：第 ② 版的病根是「排列树本来就会把同一个组合数很多遍」。
// 换一棵树就没这个病了 —— 第 3 章讲子集时那棵树，每层决定的是
// **「第 i 个数选不选」**，而不是「第 step 位放谁」。
// 一个数只有「在里面 / 不在里面」两种身份，**根本没有顺序这回事** ⇒ 天生不重复。
//
// ★★ 请特别记住这一版：**它已经能 AC 了。**
//    n < 21，整棵子集树 2^(n+1) - 1 <= 2 097 151 个节点，跑一遍连 0.1 秒都不到。
//    考场上写到这儿就该去做下一题了。
//    「不写到最优就不配交」是教科书给人的错觉 —— 能过的分和最优解的分一模一样。
//
// 为什么输出正好是字典序：每一层都先走「选」再走「不选」，
// 于是含 1 的组合全部排在不含 1 的前面，含 2 的排在不含 2 的前面……层层如此，正好是字典序。
//
// ⚠ 它仍然有一处浪费，第 ④ 版会补上：已经选够 r 个了它还继续往下走，
//    剩下的数一个都不够了它也照走不误。

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

int n, r;
int pick[25];        // pick[0..cnt-1] = 已经选进来的数

// 轮到「第 i 个数选不选」，此刻已经选了 cnt 个
void dfs(int i, int cnt) {
    if (i > n) {                                       // n 个数都表过态了
        if (cnt == r) {
            for (int k = 0; k < r; k++) printf("%3d", pick[k]);
            printf("\n");
        }
        return;
    }

    pick[cnt] = i;                                     // 选它
    dfs(i + 1, cnt + 1);

    dfs(i + 1, cnt);                                   // 不选它
    // 不用撤销：pick[cnt] 只会被「比它靠后的层」重新写掉，
    // 而读 pick 的地方只读 [0, cnt)。和第 4 章讲的判据是同一条。
}

int main() {
    if (!(cin >> n >> r)) return 0;
    if (r < 0 || r > n) return 0;
    dfs(1, 0);
    return 0;
}

// 洛谷 P1157 组合的输出 —— 第 ④ 版：给子集树加两句剪枝
//
// 输入：n r
// 输出：所有组合，字典序（和第 ③ 版逐字节相同）
//
// 这份为什么存在：第 ③ 版已经能过了，但它把功夫花在了两种明摆着没戏的地方 ——
// 这正好是第 4 章「剪枝」的预演，而且两句话就能写完：
//
//   ① 已经选够 r 个了 —— 后面的数一个都不用再问，直接输出走人；
//   ② 剩下的数**全选**都还不够 r 个 —— 这条路上一个答案都长不出来，掉头。
//
// ★ 两句都在做同一件事：**把「不可能」提前认出来，而不是走到底再发现**。
//   p1157Count.cpp 会把省下来的节点数量出来 —— n = 20、r = 10 时从 2 097 151 降到 705 431（省了三分之二）。
//
// ⚠ 剪枝**不改变答案**，只改变工作量。所以第 ③ 版和这一版的输出必须逐字节相同，
//   这一条已经写成断言（check-viz.mjs 里第 3 章那一段）。

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

int n, r;
int pick[25];

void dfs(int i, int cnt) {
    if (cnt == r) {                                    // ★ 剪枝 ①：够了，后面不用问了
        for (int k = 0; k < r; k++) printf("%3d", pick[k]);
        printf("\n");
        return;
    }
    if (cnt + (n - i + 1) < r) return;                 // ★ 剪枝 ②：剩下的全要也不够
    if (i > n) return;                                 // 兜底（有了 ② 其实走不到，留着更好读）

    pick[cnt] = i;
    dfs(i + 1, cnt + 1);
    dfs(i + 1, cnt);
}

int main() {
    if (!(cin >> n >> r)) return 0;
    if (r < 0 || r > n) return 0;
    dfs(1, 0);
    return 0;
}

// 洛谷 P1157 组合的输出 —— 第 ⑤ 版：回到排列那棵树，**只改 for 的起点**
//
// 输入：n r
// 输出：所有组合，字典序
//
// 这份为什么存在：题单里那句「从排列改成组合，只需改一个地方 —— 想清楚是哪个」说的就是它。
//
// 把第 ① 版（也就是第 3 章的 perm.cpp）和这一份并排看：
//
//     排列：for (int v = 1;     v <= n; v++) { if (used[v]) continue; ... }
//     组合：for (int v = start; v <= n; v++) { ...                        }
//                    ~~~~~~~
//
// **改的就是那个起点**：下一层不从 1 开始挑，而是从「我刚选的这个数 + 1」开始挑。
// 于是选出来的数天生递增 —— 递增的序列每个组合只有一种写法，**重复从根上就没了**。
//
// ★★ 而且改完之后 `used[]` 整个消失了，连带那句撤销也没了：
//    「不许重复用同一个数」这条规则，被**起点**这个表示法吃掉了。
//    （第 2 章那句「换个表示法就消掉一条规则」，第 4 章开头也用同一招消掉了「同行同列」。）
//
// ⚠ 别把「只改一个地方」理解成「只有这一版才对」：第 ③ 版照样 AC。
//    这一版赢在**说得清**：树上每个节点都对应一个真答案的前缀，没有一步是白走的。

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

int n, r;
int pick[25];

// 轮到选第 step 个数（0 基），只许从 start 往后挑
void dfs(int step, int start) {
    if (step == r) {
        for (int k = 0; k < r; k++) printf("%3d", pick[k]);
        printf("\n");
        return;
    }
    for (int v = start; v <= n; v++) {                 // ★ 全部的改动就在这个 start 上
        pick[step] = v;
        dfs(step + 1, v + 1);                          // 下一个只能比 v 大
    }
}

int main() {
    if (!(cin >> n >> r)) return 0;
    if (r < 0 || r > n) return 0;
    dfs(0, 1);
    return 0;
}

// 洛谷 P1157 的五个版本，各要走多少个节点 —— 换一把可复现的尺子
//
// 输入：无（直接跑，表是写死的四组 n / r，最后一组就是题目的上界）
// 输出：一张表，对每组 (n, r) 列出
//         组合数 C(n,r)     正确答案有多少行
//         ① 排列 + 去重      p1157Perm / p1157Set 走的节点数
//         ③ 子集树          p1157Subset
//         ④ 加剪枝          p1157Prune
//         ⑤ 改 for 的起点   p1157.cpp
//
// 「节点数」的定义全表统一：**dfs() 被调用了多少次**。
//
// ⚠ ① 那一列是**算出来的，不是跑出来的** —— n = 20 时它有七千多亿个节点，
//    跑不完。这本身就是这一列要说明的事：
//    Σ P(n,k)（k = 0..r）是排列树前 r 层的节点数，公式一行就写完，而秒表永远等不到它。
//    另外三列都是真跑出来的。
//
// ★ 为什么用「次数」不用秒表：秒数换台机器就变，次数不变
//   （第 21、36、38 章都是这么干的；第 4 章第 11 步刚用过同一招）。

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

int n, r;
long long nodes = 0;

/* ③ 子集树：每层决定「第 i 个数选不选」 */
void subset(int i, int cnt) {
    nodes++;
    if (i > n) return;
    subset(i + 1, cnt + 1);
    subset(i + 1, cnt);
}

/* ④ 同一棵树，加两句剪枝 */
void prune(int i, int cnt) {
    nodes++;
    if (cnt == r) return;
    if (cnt + (n - i + 1) < r) return;
    if (i > n) return;
    prune(i + 1, cnt + 1);
    prune(i + 1, cnt);
}

/* ⑤ 排列树，只把 for 的起点从 1 换成 start */
void pickFrom(int step, int start) {
    nodes++;
    if (step == r) return;
    for (int v = start; v <= n; v++) pickFrom(step + 1, v + 1);
}

/** C(n, r)：n < 21，long long 装得下（C(20,10) = 184756） */
long long comb(int a, int b) {
    long long c = 1;
    for (int i = 1; i <= b; i++) c = c * (a - b + i) / i;
    return c;
}

/** ① 排列树前 r 层的节点数 = Σ P(n,k)，k = 0..r。跑不完，只能算 */
long long permNodes(int a, int b) {
    long long total = 0, p = 1;                        // p = P(a, k)
    for (int k = 0; k <= b; k++) {
        total += p;
        p *= (a - k);                                  // P(a, k+1) = P(a, k) × (a - k)
    }
    return total;
}

long long countWith(void (*run)(int, int), int a, int b, int x, int y) {
    n = a; r = b; nodes = 0;
    run(x, y);
    return nodes;
}

int main() {
    // ⚠ 表头一律用 ASCII 的「1.」而不是「①」：圈号是「东亚宽度＝歧义」，
    //   在页面上按双宽渲染、在别的终端可能按单宽，列就歪了（同 check:text 第 ① 条那个坑）。
    cout << "  n    r    组合数     1.排列+去重     3.子集树    4.加剪枝    5.改起点\n";
    cout << "---   --   -------   -------------   ----------   ---------   ---------\n";

    const int rows[][2] = { {5, 3}, {10, 5}, {16, 8}, {20, 10} };
    for (const auto& row : rows) {
        int a = row[0], b = row[1];
        cout << setw(3) << a
             << setw(5) << b
             << setw(10) << comb(a, b)
             << setw(16) << permNodes(a, b)
             << setw(13) << countWith(subset, a, b, 1, 0)
             << setw(12) << countWith(prune, a, b, 1, 0)
             << setw(12) << countWith(pickFrom, a, b, 0, 1) << "\n";
    }

    cout << "\n第 1 列是用公式算的（它跑不完）；另外三列是真跑出来的。\n";
    return 0;
}