求一个数组的子集

92 阅读 0 评论 61 点赞

我是靠谱客的博主背后鸡翅，最近开发中收集的这篇文章主要介绍求一个数组的子集，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

该题是力扣上面的一个题，感觉思路不错就摘抄下来做个笔记。以后准备定期耍上面的题来提高一下自己的算法基础。题目描述如下：

给定一组不含重复元素的正数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解题思路如下：一个长度是n的数组其子集的个数subsetsSize=2的n次方,即subsetsSize=(int)Math.pow(2,nums.length)。换而言之数组nums的子集构成的新数组的长度就是2的n次方。而且最关键的是nums数组长度n构成的二进制数字的最大值就是subsetsSize。就比如说[1,2,3]的子集的个数是8，数组长度是3，3用二进制为011：从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]，同理110对应的子集就是[1,2]：
在这里插入图片描述

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

             int arrayIndex = 0;
            int setSizeIndex= i;
            List<Integer> temp = new ArrayList<>();
            //number=0说明当前的数不取
            while(setSizeIndex!= 0){
 
               //与运算，都是1的时候返回1
                if((setSizeIndex&1) == 1){
                    temp.add(nums[arrayIndex]);
                }
                //右移一位
                setSizeIndex=setSizeIndex>>1;
                arrayIndex++;
            }

最终实现算法如下：

    
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //子集的个数
        int setsSize = (int)Math.pow(2,nums.length);
        for(int i=0;i<setsSize;i++){
            //数组下表
            int arrayIndex = 0;
            int setSizeIndex= i;
            List<Integer> temp = new ArrayList<>();
            //number=0说明当前的数不取
            while(setSizeIndex!= 0){
               // 与运算符用符号“&”表示，其使用规律如下：
               // 两个操作数中位都为1，结果才为1，否则结果为0
                if((setSizeIndex&1) == 1){
                    temp.add(nums[arrayIndex]);
                }
                setSizeIndex=setSizeIndex>>1;
                arrayIndex++;
            }
            result.add(temp);
        }
        return result;
    }
}

算法的思路很巧妙，到此分析结束，当然也有别的解法。