如何高效生成列表中N个元素的所有非空组合（不含空集的幂集）？

你已经实现了一个递归分治的思路来生成所有非空组合，这个逻辑是完全正确的——每次拆分出第一个元素，生成它的单元素子集，再递归处理剩余元素，把递归得到的子集和当前元素组合，最后合并结果。不过咱们可以从数据结构选择和**实现方式（递归/迭代）**两个角度来优化性能，同时先拆解下你的现有实现的特点：

你的现有实现分析 #

你的递归方法的时间复杂度其实是O(n·2ⁿ⁻¹)，这已经是生成所有非空子集的最优下界了——因为每个元素会出现在2ⁿ⁻¹个子集里，所有子集的总元素数就是n·2ⁿ⁻¹，任何生成所有子集的算法都绕不开这个总操作量。不过你的代码用了std::list，它的链表结构虽然支持O(1)的splice，但元素分散存储会导致缓存命中率低，构造子集时的insert和复制操作也会因为链表的特性有额外开销。如果换成连续内存的std::vector，缓存友好性会提升很多，性能能明显改善。

更高效的实现方案 #

1. 递归优化：替换为std::vector

把std::list换成std::vector后，代码的缓存 locality更好，复制和插入操作的实际执行速度会更快。优化后的递归版本如下：

#include <vector>

template<typename T>
std::vector<std::vector<T>> GetCombinations(const std::vector<T>& input) {
    std::vector<std::vector<T>> retVal;
    if (input.size() == 1) {
        retVal.push_back(input);
        return retVal;
    }

    // 拆分第一个元素和剩余元素
    T first = input[0];
    std::vector<T> rest(input.begin() + 1, input.end());

    // 加入单元素子集
    retVal.push_back({first});

    // 递归处理剩余元素
    auto combinations = GetCombinations(rest);

    // 生成当前元素与剩余子集的组合
    for (const auto& subset : combinations) {
        std::vector<T> temp = {first};
        temp.insert(temp.end(), subset.begin(), subset.end());
        retVal.push_back(temp);
    }

    // 合并剩余元素的子集结果
    retVal.insert(retVal.end(), combinations.begin(), combinations.end());

    return retVal;
}

2. 迭代实现：避免递归栈开销

如果输入的元素数量n较大（比如n>20），递归的栈深度可能会触发栈溢出（默认栈大小一般在1~8MB，递归深度1000就会爆），这时候迭代实现更安全，同时性能也和递归相当：

#include <vector>

template<typename T>
std::vector<std::vector<T>> GetCombinationsIterative(const std::vector<T>& input) {
    std::vector<std::vector<T>> retVal;
    for (const T& elem : input) {
        // 先保存当前结果的长度，避免循环中新增的元素影响遍历
        size_t currentSize = retVal.size();
        // 生成当前元素的单元素子集
        retVal.push_back({elem});
        // 把现有每个子集都加上当前元素，生成新子集
        for (size_t i = 0; i < currentSize; ++i) {
            std::vector<T> temp = retVal[i];
            temp.push_back(elem);
            retVal.push_back(temp);
        }
    }
    return retVal;
}

这个迭代方法的逻辑是：遍历每个元素，对于每个元素，先把它的单元素子集加入结果，再把当前结果中已有的所有子集（处理当前元素前的子集）都加上这个元素，生成新的子集并加入结果。最终得到的就是所有非空子集，且保持了和输入一致的元素顺序。

性能对比 #

• 用std::vector代替std::list：在n=15时，vector版本的速度大概是list版本的3~5倍（取决于编译器和硬件），因为连续内存的缓存命中率更高，复制操作更高效。
• 迭代 vs 递归：当n较小时，两者性能差不多；当n较大时，迭代避免了递归的栈帧开销，更稳定且略快。

内容来源于stack exchange