为了确保你的 OJ 测试数据既专业又高效，我为你准备了基于 C++14 标准 的数据生成器（非递归迭代版）和配套的 SPJ（Special Judge）。

全排列、子集等问题的输出量随 $n$ 呈指数级增长，本方案将 $n$ 最高控制在 $15$ 左右，以保证 .out 文件大小在 2MB 左右。

一、 数据生成器 (gen.cpp)

该程序通过枚举每个唯一元素的出现次数（频率）来生成所有不重复子集，完全避免了递归，确保不会爆栈。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>

using namespace std;

// 迭代生成所有不重复子集并写入文件
void generate_output(int n, vector<int>& nums, const string& filename) {
    ofstream fout(filename);
    if (!fout.is_open()) return;

    // 统计频率
    sort(nums.begin(), nums.end());
    vector<pair<int, int>> freq;
    for (int x : nums) {
        if (freq.empty() || freq.back().first != x) freq.push_back({x, 1});
        else freq.back().second++;
    }

    // current_subset 记录每个唯一元素选了多少个
    vector<int> counts(freq.size(), 0);
    
    while (true) {
        // 输出当前构造的子集
        bool first = true;
        for (int i = 0; i < freq.size(); ++i) {
            for (int j = 0; j < counts[i]; ++j) {
                if (!first) fout << " ";
                fout << freq[i].first;
                first = false;
            }
        }
        fout << "\n"; // 空集表现为一个空行

        // 模拟进位：寻找第一个可以增加的计数
        int idx = freq.size() - 1;
        while (idx >= 0 && counts[idx] == freq[idx].second) {
            counts[idx] = 0;
            idx--;
        }

        if (idx < 0) break; // 所有组合生成完毕
        counts[idx]++;
    }
    fout.close();
}

int main() {
    // 测试点设计 n 规模。n=15时，最大子集数为2^15=32768，文件约1MB
    int test_n[] = {1, 3, 10, 10, 12, 14, 15, 12, 15, 15};
    // 元素分布特征
    // 1: 边界, 2: 样例, 3: 全相同, 4: 全不同, 5-10: 混合重复
    
    for (int t = 1; t <= 10; ++t) {
        int n = test_n[t - 1];
        string in_name = to_string(t) + ".in";
        string out_name = to_string(t) + ".out";

        vector<int> nums;
        if (t == 2) nums = {1, 2, 2};
        else if (t == 3) for(int i=0; i<n; ++i) nums.push_back(7);
        else {
            for(int i=0; i<n; ++i) {
                // 利用 t 控制重复率
                if (t % 2 == 0) nums.push_back(i); // 全不同
                else nums.push_back(rand() % (n / 2 + 1)); // 高重复
            }
        }

        ofstream fin(in_name);
        fin << n << "\n";
        for (int i = 0; i < n; ++i) fin << nums[i] << (i == n - 1 ? "" : " ");
        fin << "\n";
        fin.close();

        generate_output(n, nums, out_name);
        cout << "Test Case " << t << " generated.\n";
    }
    return 0;
}

二、 特判程序 (checker.cpp)

使用 testlib.h。由于子集顺序不限，SPJ 会将标准答案和用户输出都读入 set<vector<int>> 进行对比。

#include "testlib.h"
#include <vector>
#include <set>
#include <algorithm>
#include <sstream>

using namespace std;

// 将一行字符串解析为排序后的 vector
vector<int> parse_line(string line) {
    stringstream ss(line);
    vector<int> res;
    int val;
    while (ss >> val) res.push_back(val);
    sort(res.begin(), res.end());
    return res;
}

int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);

    // 1. 读入标准答案的所有子集
    set<vector<int>> ans_sets;
    while (!ans.seekEof()) {
        ans_sets.insert(parse_line(ans.readLine()));
    }

    // 2. 读入用户输出的所有子集
    set<vector<int>> ouf_sets;
    int user_line_count = 0;
    while (!ouf.seekEof()) {
        user_line_count++;
        vector<int> curr = parse_line(ouf.readLine());
        if (ouf_sets.count(curr)) {
            quitf(_wa, "第 %d 行输出了重复的子集", user_line_count);
        }
        ouf_sets.insert(curr);
    }

    // 3. 比较
    if (ouf_sets.size() < ans_sets.size()) {
        quitf(_wa, "子集数量不足：期望 %d，实际 %d", (int)ans_sets.size(), (int)ouf_sets.size());
    }
    if (ouf_sets.size() > ans_sets.size()) {
        quitf(_wa, "输出了多余的子集：期望 %d，实际 %d", (int)ans_sets.size(), (int)ouf_sets.size());
    }

    for (const auto& s : ouf_sets) {
        if (!ans_sets.count(s)) {
            quitf(_wa, "输出了一个错误的子集");
        }
    }

    quitf(_ok, "答案正确，共 %d 个唯一子集。", (int)ans_sets.size());
    return 0;
}

三、 读题与理解关键词总结（NOI 辅导专版）

在 NOI 赛场上，面对“子集”类搜索题，读题时要迅速定位以下关键词：

1. “不重复的子集” (Unique Subsets)：

   • 含义：如果输入有重复（如 2, 2），结果不能有两个 {2}。
   • 技巧：必须 排序 后通过 i > start && nums[i] == nums[i-1] 剪枝。

2. “任意顺序” (In any order)：

   • 含义：暗示后台有 SPJ。你可以选择最方便写的搜索顺序（通常是 DFS 序）。
   • 技巧：不必纠结于输出顺序，把精力放在剪枝逻辑和 I/O 速度上。

3. “整数序列” (Integer Collection)：

   • 注意点：检查元素是否有负数。如果有负数且涉及“和”的限制（如子集和问题），剪枝逻辑（如 sum > target）可能失效。

4. “空集” (Empty set)：

   • 细节：很多同学会漏掉空集。在 DFS 启动时，第一个记录的状态往往就是空集。

四、 时间复杂度优化建议 (NOI 竞赛视角)

• 避免冗余排序： 在递归内部进行 sort 是大忌（$O(N \cdot N!)$ 或 $O(N \cdot 2^N)$）。务必在 main 函数中一次性排好序。
• 传引用而非传值： dfs(vector<int> path) 会在每层递归拷贝数组，导致 $O(N^2 \cdot 2^N)$。必须使用 dfs(vector<int>& path) 配合 push_back/pop_back 回溯。
• 位运算限度： 虽然位运算（Bitmask）可以枚举子集，但在处理 重复元素 时，位运算需要配合 std::set 去重，这会增加 $O(\log(2^N))$ 的开销。此时 排序+搜索剪枝 是时间复杂度的最优解。

教练寄语： “去重”是搜索算法的必修课。这道题的 i > start 剪枝逻辑被称为“树层去重”。请记住，在搜索树中，同一层不能选相同的数，但父子节点（不同层）是可以选相同数的。掌握了这一点，你就掌握了组合类搜索的精髓！加油！

同学，处理带重复元素的搜索问题，是从“基础选手”迈向“省选选手”的分水岭。处理重复的核心思想只有四个字：规定顺序。

下面我们分三个阶段来实现这个算法。

版本一：暴力搜索 + Set 去重 (Brute Force)

这是最容易想到的办法：先不管重复，把所有子集都搜出来，把每个子集排序后扔进 std::set 里利用集合的唯一性去重。

思考过程：

• 时间复杂度：$O(2^n \cdot n \log n)$。生成 $2^n$ 个子集，每个子集排序并插入 set 的代价是 $O(n \log n)$。
• 空间复杂度：$O(n \cdot 2^n)$。需要存储所有子集，内存开销巨大。
• 评价：在 $n \le 12$ 时能过，但不是竞赛推荐做法，容易 MLE（内存超限）。

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

using namespace std;

int n;
int a[25];
vector<int> path;
set<vector<int>> res; // 利用 set 自动去重

void dfs(int u) {
    if (u == n) {
        vector<int> tmp = path;
        sort(tmp.begin(), tmp.end()); // 排序后才能去重
        res.insert(tmp);
        return;
    }
    // 不选
    dfs(u + 1);
    // 选
    path.push_back(a[u]);
    dfs(u + 1);
    path.pop_back(); // 回溯
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];

    dfs(0);

    for (const auto& subset : res) {
        for (int i = 0; i < subset.size(); ++i)
            cout << subset[i] << (i == subset.size() - 1 ? "" : " ");
        cout << "\n";
    }
    return 0;
}

版本二：最优复杂度——排序 + 树层剪枝 (Optimal Pruning)

这是 NOI 竞赛中的标准解法。通过预先排序，在搜索树的“同一层”进行去重。

思考过程：

• 核心逻辑：如果当前层的循环中，选取的数和前一个数相同，且前一个数在当前层已经尝试过了，就直接跳过。
• 时间复杂度：$O(n \cdot 2^n)$。注意，这里的 $2^n$ 是上限，实际搜索次数远小于它。
• 空间复杂度：$O(n)$。不需要存储所有结果，边搜边输出。

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

using namespace std;

int n;
int a[25];
vector<int> path;

void dfs(int start) {
    // 关键点 1：每进入一次 dfs，当前的 path 就是一个唯一的子集，直接输出
    for (int i = 0; i < path.size(); ++i)
        cout << path[i] << (i == path.size() - 1 ? "" : " ");
    cout << "\n";

    for (int i = start; i < n; ++i) {
        // 关键点 2：树层剪枝
        // 如果 i > start，说明 nums[i-1] 在当前层已经被考虑过了
        // 因为数组是有序的，nums[i] == nums[i-1] 表示这两个数是重复的
        // 我们只选第一个出现的重复数字作为本层开头的分支
        if (i > start && a[i] == a[i - 1]) continue;

        path.push_back(a[i]);
        dfs(i + 1); // 递归进入深层
        path.pop_back(); // 回溯
    }
}

int main() {
    // 竞赛建议：使用快速输出，并避免 endl
    ios::sync_with_stdio(false); cin.tie(0);

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

    // 关键点 3：处理重复必须先排序！
    sort(a, a + n);

    dfs(0);

    return 0;
}

三、 复杂度分析与时间优化建议

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

• 排序阶段：$O(n \log n)$。
• 搜索阶段：
  • 如果没有重复元素，状态数为 $2^n$。
  • 有重复元素时，状态数显著减少。例如 $\{2, 2, 2, 2\}$，子集只有 5 个（空, {2}, {2,2}, {2,2,2}, {2,2,2,2}）。
  • 单次输出代价为 $O(n)$。
• 结论：总复杂度 $O(n \cdot 2^n)$。在 $n=20$ 且元素全部重复时极快，元素互不相同时约为 $10^6$ 次操作，安全通过。

2. 空间复杂度分析

• 递归开销：$O(n)$ 栈空间。
• 路径存储：$O(n)$。
• 优化建议：在 NOI 考场上，如果输出量巨大，建议使用 printf 或者手写 Fast I/O。因为 cout 即使关闭同步，在大规模循环输出中仍可能成为瓶颈。

3. 为什么是 i > start 而不是 i > 0？

这是很多同学容易写错的地方：

• i > 0：会把 {1, 2, 2} 中的第二个 2 给误杀掉，导致你搜不出 {2, 2} 这个合法子集。
• i > start：它只限制“同一层递归”不能选重复的数，但不限制“深层递归”去选后面那个重复的数。这样就保证了我们能选出多个重复的数，但不会选出重复的组合。

四、 总结：读题关键词与应试技巧

1. 关键词：重复 (Duplicates)

   • 看到重复，第一反应是 sort。
   • 第二反应是搜索中的 if (i > start && a[i] == a[i-1])。

2. 关键词：子集 (Subsets)

   • 确定是 DFS 模型。
   • 确定状态总数约 $2^n$。
   • 如果 $n > 25$，则子集枚举通常不可行，需考虑 DP 或折半搜索 (Meet-in-the-middle)。

3. 调试建议

   • 如果发现输出多了：检查剪枝条件是否漏写或写错。
   • 如果发现输出少了：检查是不是把 i > start 写成了 i > 0。
   • 如果结果完全不对：检查是否忘记了在 main 函数里进行排序。

教练点评： 这道题是搜索算法的“去重模版”。在 NOI 考试中，很多复杂的动态规划（DP）或高级搜索（如选课、背包变体）本质上都是在这套代码的基础上增加特定的限制条件。务必把这几行剪枝逻辑背到肌肉记忆里！加油！