C++如何获取字符串的所有子序列-C++-PHP中文网

子序列生成本质是位运算枚举，每个字符“选/不选”对应二进制位0/1，n长字符串共2^n个子序列；最高效方式是用mask从0到(1j)&1判断第j位，避免递归与额外开销。

c++如何获取字符串的所有子序列

子序列生成的本质是位运算枚举

字符串的每个字符只有“选”或“不选”两种状态，长度为 n 的字符串共有 2^n 个子序列（含空串）。暴力回溯可行，但最直接、高效且无递归开销的方式是用整数 i 从 0 到 (1 枚举所有掩码，再按位判断哪些位置被选中。

用 `std::bitset` 或位运算提取字符

对每个掩码 i，遍历字符串下标 j，检查 i & (1 是否为真。注意：<code>1 在 <code>j >= 31（32 位 int）时会溢出，所以应使用 unsigned long long 掩码或确保 n ；更稳妥的做法是用 <code>(i >> j) & 1 避免移位越界。

推荐写法：if ((mask >> j) & 1) —— 安全、清晰、无平台依赖
避免写法：if (mask & (1 —— 当 <code>j >= sizeof(int)*8 时未定义行为
若需去重（如原串含重复字符），不能靠集合自动去重：子序列相同但来源位置不同仍算同一子序列，需用 std::set<:string></:string> 手动判重

处理空串和内存效率问题

空串 "" 是合法子序列，对应掩码 0，必须包含。但若输入字符串很长（比如 n = 20 就有百万级子序列），全部存入 std::vector<:string></:string> 会快速耗尽内存。实际中往往只需要逐个处理（例如找最长回文子序列），此时应改为回调函数或生成器风格：

C++

"空空如也"

下载

void generateSubsequences(const std::string& s, 
                          std::function<void std::string> callback) {
    int n = s.size();
    for (unsigned long long mask = 0; mask > j) & 1) sub += s[j];
        }
        callback(sub);
    }
}
</void>

这样避免一次性分配所有子序列内存，也便于 early-return 或过滤。

Python 对比提醒：C++ 没有内置 `itertools.combinations`

有人想套用 Python 思路，对每个长度 k 调用 std::next_permutation 生成组合——这不仅复杂度更高（要嵌套循环 + 构造布尔向量），还容易因 std::next_permutation 要求初始升序而引入额外排序开销。位运算是 C++ 下最贴近本质、最容易写出正确代码的方式。唯一要注意的是 1 必须用足够宽的无符号类型，否则 <code>n > 31 时循环直接不执行。

真正卡住人的地方不是逻辑，而是 1 的类型隐式提升和循环上限计算——它悄无声息地截断，让你漏掉后半部分子序列。