给你一个整数数组nums数组中的元素互不相同。返回该数组所有可能的子集幂集。解集不能包含重复的子集。你可以按任意顺序返回解集。示例 1:输入nums [1,2,3]输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2:输入nums [0]输出[[],[0]]提示1.ℎ10−10[]10中的所有元素互不相同中的所有元素互不相同中的所有元素互不相同代码class Solution { public: vectorvectorint subsets(vectorint nums) { vectorvectorint res; // 存储所有子集 int n nums.size(); // 数组长度 int total 1 n; // 子集总数2^n等价于pow(2, n)位运算更高效 // 遍历所有状态0 ~ 2^n - 1每个状态对应一个子集 for (int state 0; state total; state) { vectorint path; // 存储当前子集 // 遍历当前状态的每一位判断是否选中对应元素 for (int k 0; k n; k) { // 核心用你的模板提取state的第k位数字 if ((state k) 1) path.push_back(nums[k]); // 第k位为1选中nums[k] } res.push_back(path); // 将当前子集加入结果 } return res; } };代码分析一、先搞懂核心思想二进制 子集的「选择状态」数组的每个元素只有两种选择选或不选这刚好对应二进制的「1」和「0」。比如数组nums [1,2,3]长度 3用 3 位二进制数表示所有选择可能3 位对应 3 个元素每一位对应一个元素第 0 位对应nums[0]1第 1 位对应nums[1]2第 2 位对应nums[2]3二进制位为1→ 选这个元素为0→ 不选。可视化对应关系最关键十进制 state二进制3 位第 2 位对应 3第 1 位对应 2第 0 位对应 1选中的元素子集00000不选0不选0不选[]1001001选[1]201001选0[2]3011011[1,2]41001选00[3]5101101[1,3]6110110[2,3]7111111[1,2,3]可以看到0~7共 8 个即 2³个十进制数刚好对应数组 [1,2,3] 的所有 8 个子集。二、逐行拆解代码结合上面的例子vectorvectorint res; // 存储所有子集 int n nums.size(); // 数组长度例子中n3 int total 1 n; // 子集总数13 8等价于2³位运算更快res最终要返回的所有子集比如例子中最后是[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]total子集的总数数组长度为 n 时子集数是 2ⁿ每个元素有选 / 不选两种可能。for (int state 0; state total; state) { vectorint path; // 存储当前子集比如state1时path[1]外层循环遍历所有「选择状态」例子中 state 从 0 到 7每个 state 对应一个子集path临时存储当前 state 对应的子集每次循环都会重新初始化比如 state0 时 path 是空state1 时 path 装 [1]。for (int k 0; k n; k) { if ((state k) 1) path.push_back(nums[k]); }内层循环检查当前 state 的每一位对应数组的每个元素判断是否选中该元素核心操作(state k) 1提取 state 的第 k 位你的位运算模板结果是 0 或 1例子 1state1二进制 001k0 →(1 0) 1 1 1 1→ 选中 nums [0]1例子 2state1k1 →(1 1) 1 0 1 0→ 不选 nums [1]2例子 3state4二进制 100k2 →(4 2) 1 1 1 1→ 选中 nums [2]3path.push_back(nums[k])如果第 k 位是 1就把 nums [k] 加入当前子集。res.push_back(path); // 将当前子集加入结果 } return res;把当前 state 对应的子集path加入最终结果 res循环结束后res 就包含了所有子集。三、用一个具体 state 走一遍流程彻底理解以nums [1,2,3]state5二进制 101为例外层循环 state5初始化 path 为空内层循环 k0(5 0) 1→ 5 的二进制是 101右移 0 位还是 101和 1 按位与 → 1 → 选中 nums [0]1 → path[1]内层循环 k1(5 1) 1→ 5 右移 1 位是 10二进制和 1 按位与 → 0 → 不选 nums [1]2内层循环 k2(5 2) 1→ 5 右移 2 位是 1二进制和 1 按位与 → 1 → 选中 nums [2]3 → path[1,3]把 path[1,3] 加入 res这就是 state5 对应的子集 [1,3]。四、核心疑问解答新手最常问1. 为什么是「state k 1」而不是其他「state k」把 state 的第 k 位移到「个位」比如 state5101k2 时右移 2 位变成 1第 2 位就到了个位「 1」只保留个位0 或 1就能知道第 k 位是 0 还是 1对应不选 / 选。2. 为什么子集总数是「1 n」「1 n」是位运算等价于 2 的 n 次方n3 时13 80~7 共 8 个数n2 时12 40~3 共 4 个数对应 [1,2] 的 4 个子集[], [1], [2], [1,2]。3. 数组长度 n10 时state 会很大吗n10 时total1101024state 从 0 到 1023完全在 int 的范围里int 能存到 2¹⁶左右不用担心溢出。五、总结核心逻辑一句话用「十进制数 state」表示子集的选择状态通过「位运算提取 state 的每一位」判断是否选中对应元素遍历所有 state 就能生成所有子集。整个代码的逻辑就是枚举所有选择状态 → 解析每个状态对应的元素 → 收集所有子集而位运算是解析状态的「高效工具」。class Solution { public: vectorvectorint subsets(vectorint nums) { const int n nums.size(); // 1. 常量优化避免重复读取size()编译器可优化 const int total 1 n; // 2. 提前计算总数避免循环内重复计算 // 3. 预分配内存避免vector频繁扩容最核心的效率优化 vectorvectorint res; res.reserve(total); // 直接预留2^n个位置减少多次扩容的拷贝开销 // 4. 外层循环用int→unsigned int避免符号位干扰编译器生成更高效的指令 for (unsigned int state 0; state total; state) { vectorint path; // 5. 提前预估path大小可选减少path的扩容次数 int cnt __builtin_popcount(state); // GCC内置函数O(1)统计1的个数 path.reserve(cnt); // 6. 内层循环用k→k编译器优化且kn改为k!n少数编译器更友好 for (int k 0; k ! n; k) { // 7. 位运算顺序优化先1再判断逻辑不变但指令更紧凑 if ((state k) 1) { path.push_back(nums[k]); } } res.push_back(std::move(path)); // 8. 移动语义避免path的拷贝直接转移内存 } return res; } };相似题目子集 II中等列举单词的全部缩写中等字母大小写全排列中等从子集的和还原数组困难统计按位或能得到最大值的子集数目中等136. 只出现一次的数字难度简单相关标签位运算、数组题目给你一个非空整数数组nums除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。示例 1:输入nums [2,2,1]输出1示例 2:输入nums [4,1,2,1,2]输出4示例 3:输入nums [1]输出1提示1.ℎ3∗104−3∗104[]3∗104除了某个元素只出现一次以外其余每个元素均出现两次。除了某个元素只出现一次以外其余每个元素均出现两次。除了某个元素只出现一次以外其余每个元素均出现两次。代码class Solution { public: int singleNumber(vectorint nums) { int res 0; // 初始化为0利用n^0n的性质 for (int num : nums) res ^ num; // 核心依次异或所有元素重复元素抵消为0 return res; } };相似题目只出现一次的数字 II中等只出现一次的数字 III中等丢失的数字简单寻找重复数中等找不同简单求出出现两次数字的 XOR 值简单338. 比特位计数难度简单相关标签位运算、动态规划题目给你一个整数n对于0 i n中的每个i计算其二进制表示中1的个数返回一个长度为n 1的数组ans作为答案。示例 1:输入n 2输出[0,1,1]解释0 -- 01 -- 12 -- 10示例 2:输入n 5输出[0,1,1,2,1,2]解释0 -- 01 -- 12 -- 103 -- 114 -- 1005 -- 101提示0105代码class Solution { public: int lowbit(int x) { return x (-x); } vectorint countBits(int n) { vectorint cnt(n 1, 0); for (int i 1; i n; i) { int j i; while(j) { cnt[i] ; j - lowbit(j) ; } } return cnt; } };相似题目位1的个数简单计算 K 置位下标对应元素的和简单找出数组中的 K-or 值简单461. 汉明距离难度简单相关标签位运算题目两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。给你两个整数x和y计算并返回它们之间的汉明距离。示例 1:输入x 1, y 4输出2解释1 (0 0 0 1)4 (0 1 0 0)↑ ↑上面的箭头指出了对应二进制位不同的位置。示例 2:输入x 3, y 1输出1提示0,231−1代码class Solution { public: int lowbit(int x) { return x (-x); } int hammingDistance(int x, int y) { int diff x ^ y; // 异或不同位为1相同位为0 int count 0; // 统计1的个数即汉明距离 // 复用lowbit统计1的个数 while (diff 0) { count; diff - lowbit(diff); // 消去最右边的1 } return count; } };