位运算生成子集适用于n≤20的数组，每个子集对应一个n位二进制数，第i位为1表示选arr[i]，为0表示跳过，子集总数为2ⁿ。
用位运算生成所有子集最直接
数组长度 n 不大（通常 ≤ 20）时，位运算是最轻量、最易理解的方案。每个子集对应一个 n 位二进制数：第 i 位为 1 表示选中 arr[i]，为 0 表示跳过。
关键点在于：子集总数是 1 （即 <code>2^n），循环从 0 到 (1 即可遍历全部组合。
常见错误是循环上界写成 1 而没减 1，导致越界访问或重复生成空集；另一个坑是误用 <code>i & (1 的括号，漏掉会导致优先级错误（<code>& 优先级低于 ）。
示例逻辑：
立即学习“C++免费学习笔记（深入）”；
vector<vector<int>> subsets(vector<int>& arr) {
int n = arr.size();
vector<vector<int>> res;
for (int mask = 0; mask < (1 << n); ++mask) {
vector<int> subset;
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) { // 注意括号！
subset.push_back(arr[i]);
}
}
res.push_back(subset);
}
return res;
}
递归回溯适合需要剪枝或定制逻辑的场景
当你要在生成过程中提前终止（比如只找和为某值的子集）、或需控制元素顺序/去重（如输入含重复元素）、或内存受限不能一次性存全部结果时，递归回溯更灵活。
核心是维护一个当前路径 path 和起始索引 start，每次决定“是否选 arr[i]”，然后递归处理后续位置。
容易忽略的细节：
- 必须在递归调用前把当前元素加入
path，调用后立即pop_back()—— 否则状态污染 - 如果不希望重复子集（如输入为
[1,2,2]），得先排序 + 跳过相同元素的重复选择，即if (i > start && arr[i] == arr[i-1]) continue - 传
path时建议用引用+回溯，而非值传递，否则性能急剧下降
std::next_permutation 不能直接用来求幂集
有人误以为可以用 next_permutation 配合 0/1 标记数组来生成子集，但这是低效且易错的思路。原因有三：
第一，next_permutation 生成的是全排列，不是组合；要模拟子集，得先构造长度为 n 的 {0,0,...,1,1} 数组，再对每种 1 的个数分别调用 —— 复杂度陡增。
第二，它要求输入有序，且会修改原数组，和幂集生成无序、独立的语义不匹配。
第三，无法自然支持动态长度子集（比如只要大小 ≤ k 的子集），而位运算或回溯可以轻松加条件过滤。
简言之：别绕路。用 next_permutation 求幂集，就像用锤子拧螺丝 —— 不是做不到，是设计意图完全错位。
注意数据类型溢出和内存爆炸风险
幂集大小是指数级的。当 n = 25，子集数量已超 3300 万；n = 32 就超过 42 亿 —— 这时 int 作为 mask 已不够，必须用 long long 或 unsigned long long，但更现实的做法是根本别生成全部。
实际项目中，如果只是要“检查是否存在某个满足条件的子集”，应改用动态规划（如 0-1 背包）、折半搜索，或迭代式生成 + 即时判断并提前返回。
另一个常被忽视的点：C++ 中 vector<vector>></vector> 存储所有子集时，小数组（如 int[3]）反复拷贝开销不小。若只读使用，考虑返回 const vector<vector>>&</vector> 或改用索引映射避免冗余存储。
