⼆进制枚举

• 利⽤⼆进制枚举时，会⽤到⼀些位运算的知识。
• 关于⽤⼆进制中的 0/1 表⽰状态这种⽅法，以后在讨论状态压缩 dp 中会继续使⽤到。
• ⼆进制枚举的⽅式也可以⽤递归实现，后续在讨论

题目链接：78. 子集 - 力扣（LeetCode）

1.题目分析

子集：在已知的集合里，随意拿一些数组成新的集合就是子集，空集也是子集

2.算法原理

选子集就是针对某一个数而言，选或者不选，比如集合[1,2,3]，不选2，选[1,3]，看上图0-8的二进制表示，用0表示不选某一位的数，用1表示选择某一位的数，可以用0-7这8个二进制串把所有情况都枚举出来，倒数第一位是0，第二位是1，接着2，接着3，根据前面8个数的二进制表示，就可以把每一位选或者不选所有的情况都枚举出来，对应的情况正好是这道题的答案，

1.枚举二进制(0~1 << n) - 1之间所有的数，当前集合有3位，二进制1左移3位是8，0循环到7就有8次了，所以仅需枚举到8-1就可以了，假设集合里有n个元素，就有2^n个子集，(1<<n) - 1，枚举n-1个数得出相应的子集

2.根据枚举的数中二进制表示中1的位置，把相应的数选出来，二进制枚举其实就是用01串来表示某种状态，通过01串的组合，把所有的情况都枚举出来

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {//返回二维数组，ret统计vector<vector<int>> ret;int n = nums.size();//枚举所有的状态 000~111，n-1for(int st = 0; st < (1 << n); ++st){// 根据 st 的状态，还原出要选的数vector<int> tmp; //从当前选的子集//从第0位到n-1位所有的位数哪一位等于1//7=111,111&111=111, i=1,2,3条件都为真for(int i = 0; i < n; ++i){if ((st >> i) & 1) tmp.push_back(nums[i]);}ret.push_back(tmp);}return ret;}
};