同学，可复选全排列在竞赛中虽不常作为独立大题出现，但它是构建复杂搜索状态（如 $N$ 进制枚举）的基础。既然是“放飞自我”，我们就要从逻辑最清晰的版本出发，进化到竞赛级的最优性能版本。

版本一：基础递归回溯（逻辑最清晰版）

这个版本直接去掉了标准全排列中的 used 数组，每一层都拥有完整的选择权。

思考过程：

• 核心逻辑：递归深度为 $n$，每一层都有 $n$ 个分支。
• 复杂度：时间 $O(n \cdot n^n)$，空间 $O(n)$。
• 关键点：递归前先对原数组排序，可保证输出序列按字典序排列。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int nums[10];
int path[10];

// depth: 当前正在填第几个位置
void dfs(int depth) {
    // 递归边界：位置填满了
    if (depth == n) {
        for (int i = 0; i < n; ++i) {
            cout << path[i] << (i == n - 1 ? "" : " ");
        }
        cout << "\n"; // 易错点：千万不要用 endl，会频繁刷新缓冲区导致超时
        return;
    }

    // 关键：放飞自我，不再检查 used 标记
    for (int i = 0; i < n; ++i) {
        path[depth] = nums[i]; // 每一层都可以重新选 nums 中的任何数
        dfs(depth + 1);        // 递归进入下一层
    }
}

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(0); // 竞赛必备：解绑流以加速 I/O

    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; ++i) cin >> nums[i];

    // 为了符合字典序输出，必须先排序
    sort(nums, nums + n);

    dfs(0);

    return 0;
}

版本二：非递归迭代（N 进制计数器版）

这种写法能让你深刻理解：可复选全排列本质上就是一个 $n$ 进制计数器。

思考过程：

• 原理：用一个数组 idx[n] 记录每个位置选了 nums 里的第几个数。模拟加法进位逻辑。
• 优势：避免了递归调用产生的栈开销（尽管 $n=7$ 时影响较小，但在 $n$ 较大时更有利）。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a.begin(), a.end());

    // idx 存储当前每个位置对应 nums 数组的下标
    vector<int> idx(n, 0);

    while (true) {
        // 输出当前状态
        for (int i = 0; i < n; ++i) {
            cout << a[idx[i]] << (i == n - 1 ? "" : " ");
        }
        cout << "\n";

        // 进位逻辑：从最后一位开始加 1
        int pos = n - 1;
        while (pos >= 0) {
            idx[pos]++;
            if (idx[pos] < n) break; // 没满 n，不需要进位，跳出
            idx[pos] = 0;            // 满了 n，归零，向高位进位
            pos--;
        }

        if (pos < 0) break; // 最高位也产生进位了，说明全跑完了
    }
    return 0;
}

版本三：竞赛最优复杂度优化版（极速输出）

当 $n=7$ 时，$7^7 = 823,543$ 行。本题真正的瓶颈不在算法（算法复杂度已死封在 $O(n^n)$），而在 I/O 输出。

思考过程：

• 优化点：使用 printf 或手写 putchar 优化的快写。
• 空间开销：由于 $n$ 极小，递归开销可以忽略，重点是减少函数调用中的多余运算。

#include <cstdio>
#include <algorithm>

using namespace std;

int n;
int a[10];
int path[10];

// 竞赛技巧：使用 printf 替代 cout，或使用字符数组缓冲区一次性构建行
void dfs(int depth) {
    if (depth == n) {
        for (int i = 0; i < n; ++i) {
            // printf 性能优于未解绑的 cout，但慢于解绑后的 cout + \n
            // 这里使用简易循环输出
            printf("%d%c", path[i], i == n - 1 ? '\n' : ' ');
        }
        return;
    }

    for (int i = 0; i < n; ++i) {
        path[depth] = a[i];
        dfs(depth + 1);
    }
}

int main() {
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

    sort(a, a + n);

    dfs(0);

    return 0;
}

复杂度分析与建议

1. 时间复杂度分析思考过程

• 状态爆炸：每一位有 $n$ 种选择，共有 $n$ 位，总状态数为 $n^n$。
• 打印代价：每个状态需要打印 $n$ 个数。
• 总时间：$O(n \cdot n^n)$。
• 数据量验证：
  • $n=7, n^n = 823,543$。
  • $823,543 \times 7 \approx 5.7 \times 10^6$。
  • 在 NOI 机器上，每秒约处理 $10^8$ 次运算，但输出操作较慢。实际上，$7^7$ 已经是这类题目作为输出全集题的上限了。

2. 空间复杂度分析

• 递归深度：$O(n)$。$n=7$ 的递归深度对计算机来说微乎其微（系统栈轻松支持数万层）。

3. 性能优化建议

1. 行末空格处理：i == n - 1 ? '\n' : ' ' 虽然简洁，但在超大规模循环中会增加分支预测开销。追求极致时，可以先输出 $n-1$ 个带空格的数，最后单独输出带换行的数。
2. I/O 模式：在 NOI 赛场上，如果你发现 $n=8, 9$（$9^9$ 约 3.8 亿），这道题就一定不是让你输出所有解，而是求方案数或满足某种条件的解。

读题关键词总结

做 NOI 题目时，看到以下关键词，要立刻联想到本题模型：

1. “可重复选取” (Replacement/Reuse)：直接删除 used 剪枝逻辑。
2. “不限次数”：同上。
3. “按字典序” (Lexicographical order)：要求你在搜索前进行 sort。
4. “总方案数为 $n^n$”：意味着搜索树是完全对称的满 $n$ 叉树。

教练点评： 这道题是搜索算法的“减法”。从“受限排列”退化到“自由排列”，虽然逻辑变简单了，但它让你第一次直面 状态爆炸。在竞赛中，理解什么时候该“放飞自我”，什么时候该“严加管束”（剪枝），是区分中级选手和高级选手的关键。加油！