求一个数组的子集 难点面试题

求一个数组的子集

这道题是今天老师给我们的第一道题，看似只有简单的八个字，但是对于我们这种小白来说，有点难度，听说很多有很多公司面试会用这题，通过网络搜索，借鉴他人文章，写下这篇记录文章，为以后需要留个记录，今天在这里和大家分享一下。

解题思路：一个长度是n的数组其子集的个数subsetsSize=2的n次方，代码部分如下：subsetsSize=(int)Math.pow(2,nums.length)
数组nums的子集构成的新数组的长度就是2的n次方。最关键的是nums数组长度n构成的二进制数字的最大值就是subsetsSize。
从000-111之间的长度就是子集的个数。
且0-7八个数字对应的二进制就是000 001 010 011 100 101 110 111,且原数组中的下标为0,1,2三个数，正好对应着二进制的位数。在这里以101为例，1代表着取nums对应位置的数字，0代表不取，那么101就代表着取数组nums中下标第0个和第2个位置的数字构成一个子集：[1,3]，同理111对应的子集就是[1,2,3]：

循环遍历subSets的长度0-7的每一个数字，比如以5（即101）为例，获取其二进制101的每一个位数，如果是1就将nums的index位置对应的数字添加到一个新的子集里。那么怎么判断是否是1呢，核心思想：就是依靠移位运算>>来判断101中每一个位数跟1进行&运算判断是否是1即可：

下面是测试

文章引用：https://blog.****.net/chunqiuwei/article/details/88755867