算法题每日一练---第52天：位运算求解子集

一、问题描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

题目链接：位运算求解子集。

二、题目要求

样例 1

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

样例 2

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

考察

1.位运算中等题型
2.建议用时20~35min

三、问题分析

本题是位运算的第7题，没了解过位运算相关知识点可以看这一篇文章，讲解比较详细：

子集和位运算有什么关系，3个不同整数构成的最大子集为2^3，二进制也就是111。

以1 2 3的子集为例：

序号	子集	二进制
0	空集	000
1	1	001
2	2	010
3	1,2	011
4	3	100
5	1,3	101
6	2,3	110
7	1,2,3	111

看了上面的表格，是不是感觉子集都有一个不同的二进制数字对应啊！

那不就好办吗？两重循环判断就可以搞定：

第一重 for 循环

要有的二进制类型，从第一个依次向最后一个递进，最小的就是0，最大的为(1<<n)向左移动n个运算，这是左移运算符，逐步加一。

第二重 for 循环

这个要判断当前的数字是不是属于相关的二进制数组，j从0~n开始计算。

i&(1<<j)用来判断是否和当前的二进制数组相等。

四、编码实现

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int i,j,n=nums.size();
        vector<int> t;//数组定义
        vector<vector<int>> ans;//数组定义
        for(i=0;i<(1<<n);i++)//二进制组合匹配
        {
            t.clear();//清空t
            for(j=0;j<n;j++)//数字判断
            {
                if(i&(1<<j))
                {
                    t.push_back(nums[j]);//属于当前数组
                }
            }
            ans.push_back(t);
        }
        return ans;//输出结果
    }
};

五、测试结果