求n个数字全划分（元素仅用一次）的算法实现问题

你要解决的是集合的所有无序分拆问题：要求每个元素恰好出现一次，且不考虑子集内元素的顺序，也不考虑子集之间的顺序（比如[[1,2],[3]]和[[3],[1,2]]视为同一划分，[[2,1],[3]]也和它们等价）。用std::next_permutation确实不合适，因为排列会把同一划分的不同排列形式当成不同结果，必然会产生大量重复。

正确思路：递归构造法 #

核心逻辑是基于已有元素的划分，逐步添加新元素来生成所有不重复的划分：

• 假设已经得到前k个元素的所有不重复划分；
• 处理第k+1个元素时，有两种选择：
  1. 将该元素插入到当前划分的任意一个子集中；
  2. 将该元素作为独立的新子集加入当前划分；
• 递归执行这个过程直到所有元素都被处理，就能得到所有无重复的划分。

这种方法不会产生重复的根本原因：我们按元素顺序（比如从1到n）依次添加，子集内元素始终保持递增顺序（不会出现[2,1]这类逆序子集），且每个划分只会被生成一次。

C++ 代码实现 #

#include <iostream>
#include <vector>
using namespace std;

// 打印单个划分
void printPartition(const vector<vector<int>>& partition) {
    cout << "[";
    for (size_t i = 0; i < partition.size(); ++i) {
        cout << "[";
        for (size_t j = 0; j < partition[i].size(); ++j) {
            if (j > 0) cout << ", ";
            cout << partition[i][j];
        }
        cout << "]";
        if (i < partition.size() - 1) cout << ", ";
    }
    cout << "]\n";
}

// 递归生成划分：current为当前已构造的划分，nextNum为下一个要添加的数字，n为总元素数
void generatePartitions(vector<vector<int>> current, int nextNum, int n) {
    if (nextNum > n) {
        printPartition(current);
        return;
    }

    // 选项1：将nextNum插入到当前划分的每个子集中
    for (size_t i = 0; i < current.size(); ++i) {
        vector<vector<int>> newPartition = current;
        newPartition[i].push_back(nextNum);
        generatePartitions(newPartition, nextNum + 1, n);
    }

    // 选项2：将nextNum作为新子集加入当前划分
    vector<vector<int>> newPartition = current;
    newPartition.push_back({nextNum});
    generatePartitions(newPartition, nextNum + 1, n);
}

int main() {
    int n = 3;
    // 初始状态：第一个元素单独作为一个子集
    generatePartitions({{1}}, 2, n);
    return 0;
}

输出验证 #

当n=3时，代码输出为：

[[1, 2, 3]]
[[1, 2], [3]]
[[1, 3], [2]]
[[1], [2, 3]]
[[1], [2], [3]]

这和你给出的例子本质完全一致，只是子集的顺序写法不同（比如[[1],[2,3]]和你例子中的[[2,3],[1]]是同一划分），符合你要求的无重复划分规则。

内容的提问来源于stack exchange，提问作者yunibobo