算法：求一个集合的无重复的所有子集

56 阅读 0 评论 37 点赞

我是靠谱客的博主飞快早晨，最近开发中收集的这篇文章主要介绍算法：求一个集合的无重复的所有子集，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

华为面试（二面）算法题

一：题目

/*
* 说明：求一个集合的无重复的所有子集
* 输入：输入要参与子元素个数，并逐一输入子元素
* 输出：输出这些子元素组成的所有子集
* 示例：
* 请输入数字个数：3
* 请输入第1个数字：1
* 请输入第1个数字：2
* 请输入第1个数字：3
* [1]
* []
* [2]
* [1, 2, 3]
* [1, 2]
* [3]
* [2, 3]
* [1, 3]
* 算法思想： 1：本题的思路是对输入的n个元素进行组合，而组合时的核心思想就是利用数组的下标对其进行组合
* 2：n个下标分别代表着n个元素（数组中根据下标来索取元素值），而这n个元素所组成的集合中每个元素无非就
* 2种情况：参与某子集与不参与某子集。所以我们可以将第i个元素参与某子集是将第i位置为1，不参与则置为0
* 3：步骤2中可以看做有n位，每一位都有0和1两种情况。因此我们可以用n位2进制来描述这n元素对应的每位的转
* 态。
* 4：这n位的2进制数带来的组合数就是2^n种，而从0-(2^n-1)这n个数正是这n位2进制位所组成的组合所转化的十进
* 制数。所以我们只需要将这n个数转化为二进制数，再取到这个二进制数参数比对的位（二进制数中所有位中对
* 应值为1），二进制数的位置及我们输入元素的下标。
*/

二：代码

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入数字个数：");
        int size = sc.nextInt();
        ArrayList<Integer> nums = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            int x = i+1;
            System.out.println("请输入第"+x+"个数字：");
            int num = sc.nextInt();
            nums.add(num);
        }
        Collections.sort(nums);//给集合排序（无法去重）
        ArrayList<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < Math.pow(2, nums.size()); i++) {//遍历每一种方法.Math。pow(x,y)方法可返回 x 的 y 次幂的值。
            List<Integer> list = new ArrayList<>();
            int index = i;//每个index都代表了一种组合的可能；
            // （如输入三个数时，十进制数2等于二进制数010，则只有第二位不为1代表取排好序的输入数组第二个）
            for (int j = 0; j < nums.size(); j++) {//每个可能的排序代表的数字转换成的二进制位数都不会超过输入个数
                if((index & 1)==1){//注意&是按位与 每种可能转换为二进制数后，二进制数的每一位都代表了一个排好序的输入数
                    list.add(nums.get(j));
                    //如果目前的第一位（可能移位过的）转换为二进制后位与操作后为1，则代表该位置的输入位参与该次组合
                }
                index >>= 1;//向右位移，第二位变第一位。对下一个输入位进行判断是否参与此次的组合
            }
            result.add(list);//把每次的输入组合都添加到大集合中，进行去重
        }
        Set<List<Integer>> set = new HashSet<>(result);//将list添加到set中去重
        for (List<Integer> list : set) {
            System.out.println(list);
        }
    }

-----------------------------------------------------------------底线-----------------------------------------------------------------