位运算力扣题（leetcode）

位运算力扣题（leetcode）

78. 子集

难度：中等
相关标签：位运算、数组、回溯
题目：

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2:

输入：nums = [0]
输出：[[],[0]]

提示：

• \(1  0) & 1 = 1 & 1 = 1 → 选中 nums [0]=1；
  
• 例子 2：state=1，k=1 → (1 >> 1) & 1 = 0 & 1 = 0 → 不选 nums [1]=2；
  
• 例子 3：state=4（二进制 100），k=2 → (4 >> 2) & 1 = 1 & 1 = 1 → 选中 nums [2]=3；
  

path.push_back(nums[k])：如果第 k 位是 1，就把 nums [k] 加入当前子集。
</ul>

1. class Solution
2. {
3. public:
4.     vector<vector<int>> subsets(vector<int>& nums)
5.     {
6.         vector<vector<int>> res; // 存储所有子集
7.         int n = nums.size();     // 数组长度
8.         int total = 1 << n;      // 子集总数：2^n（等价于pow(2, n)，位运算更高效）
9.         
10.         // 遍历所有状态（0 ~ 2^n - 1），每个状态对应一个子集
11.         for (int state = 0; state < total; state++)
12.         {
13.             vector<int> path; // 存储当前子集
14.             // 遍历当前状态的每一位，判断是否选中对应元素
15.             for (int k = 0; k < n; k++)
16.             {
17.                 // 核心：用你的模板提取state的第k位数字
18.                 if ((state >> k) & 1)
19.                     path.push_back(nums[k]); // 第k位为1，选中nums[k]
20.             }
21.             res.push_back(path); // 将当前子集加入结果
22.         }
23.         
24.         return res;
25.     }
26. };

复制代码

• 把当前 state 对应的子集（path）加入最终结果 res；
  
• 循环结束后，res 就包含了所有子集。
  

三、用一个具体 state 走一遍流程（彻底理解）

以 nums = [1,2,3]，state=5（二进制 101）为例：

• 外层循环 state=5，初始化 path 为空；
  
• 内层循环 k=0：
  
  
  
  • (5 >> 0) & 1 → 5 的二进制是 101，右移 0 位还是 101，和 1 按位与 → 1 → 选中 nums [0]=1 → path=[1]；
    
  
  
• 内层循环 k=1：
  
  
  
  • (5 >> 1) & 1 → 5 右移 1 位是 10（二进制），和 1 按位与 → 0 → 不选 nums [1]=2；
    
  
  
• 内层循环 k=2：
  
  
  
  • (5 >> 2) & 1 → 5 右移 2 位是 1（二进制），和 1 按位与 → 1 → 选中 nums [2]=3 → path=[1,3]；
    
  
  
• 把 path=[1,3] 加入 res；
  
• 这就是 state=5 对应的子集 [1,3]。
  

四、核心疑问解答（新手最常问）

1. 为什么是「state >> k & 1」，而不是其他？

• 「state >> k」：把 state 的第 k 位移到「个位」（比如 state=5=101，k=2 时，右移 2 位变成 1，第 2 位就到了个位）；
  
• 「& 1」：只保留个位（0 或 1），就能知道第 k 位是 0 还是 1（对应不选 / 选）。
  

2. 为什么子集总数是「1