(关注数据结构和算法，了解更多新知识)
网上看到一网友发文说收到面试邀请，面试时间竟然是早晨5点，这是要猝死的节奏。有的网友说应该是下午 5 点，如果是下午 5 点直接写下午 5 点就行了，或者写 17 点也行，直接写 5 点感觉很不专业。
也有的说可能是在国外，这种情况我也遇到过，国内和国外同时开会，如果按照国外的上班时间开会，国内有可能是在早晨 5 点。但这是面试，不是开会。
还有的说有可能是 15 点 ，少写了一个 1 ，不管怎么说这面试邀请也太敷衍了。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第78题：子集。
问题描述
来源：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 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素互不相同
问题分析
这题让返回数组的所有子集，把原数组中的某些元素去掉之后就是其中的一个子集。对于每个元素都有两种状态，一种是选择一种是不选择，所以总的子集数量是2^length，其中length是数组的长度。
这题可以通过回溯算法或者二进制来解决，对于回溯算法也有两种解决方式，这个我们后面再讲，这里我们来看下使用二进制怎么解决。
对于所有在[0，2^length)之间的数字都可以看作是原数组一个子集的表示，对于当前数字如果某一位是1就表示需要选择对应的元素，如果是0就表示不选。比如示例1中子集的选择如下：
JAVA：
public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> ans = new ArrayList<>();int total = 1 << nums.length;// 总的子集个数for (int i = 0; i < total; i++) {List<Integer> subList = new ArrayList<>();for (int j = 0; j < nums.length; j++) {// 如果数字 i 的某一位上是 1 就选择。if ((i & (1 << j)) != 0)subList.add(nums[j]);}ans.add(subList);}return ans;
}C++：
public:vector<vector<int>> subsets(vector<int> &nums) {vector<vector<int>> ans;int total = 1 << nums.size();// 总的子集个数for (int i = 0; i < total; i++) {vector<int> subList;for (int j = 0; j < nums.size(); j++) {// 如果数字 i 的某一位上是 1 就选择。if ((i & (1 << j)) != 0)subList.push_back(nums[j]);}ans.push_back(subList);}return ans;}C：
int **subsets(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {int total = 1 << numsSize;// 总的子集个数int **ans = malloc(total * sizeof(int *));*returnColumnSizes = malloc(total * sizeof(int));memset(*returnColumnSizes, 0, total * sizeof(int));*returnSize = 0;for (int i = 0; i < total; i++) {ans[*returnSize] = malloc(numsSize * sizeof(int));for (int j = 0; j < numsSize; j++) {// 如果数字 i 的某一位上是 1 就选择。if ((i & (1 << j)) != 0)ans[*returnSize][(*returnColumnSizes)[*returnSize]++] = nums[j];}(*returnSize)++;}return ans;
}Python：
def subsets(self, nums: List[int]) -> List[List[int]]:ans = []total = 1 << len(nums) # 总的子集个数for i in range(total):subList = []for j in range(len(nums)):# 如果数字 i 的某一位上是 1 就选择。if (i & (1 << j)) != 0:subList.append(nums[j])ans.append(subList)return ans
笔者简介
博哥，真名：王一博，毕业十多年，《算法秘籍》作者，专注于数据结构和算法的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以下载我整理的1000多页的PDF算法文档。
我的新书《算法秘籍》出版了。
《征服数据结构》目录
女程序员被逼哭。。
