java - 获取集合的所有子集

Question

import java.util.ArrayList;

public class Subset { //Generate all subsets by generating all binary numbers
    public static ArrayList<ArrayList<Integer>> getSubsets2(ArrayList<Integer> set) {

        ArrayList<ArrayList<Integer>> allsubsets =
            new ArrayList<ArrayList<Integer>>();
        int max = 1 << set.size();             //there are 2 power n 
        for (int i = 0; i < max; i++) {
            ArrayList<Integer> subset = new ArrayList<Integer>();

            int index = 0;
            while (i > 0) {
                if ((i & 1) > 0) {
                    subset.add(set.get(index)); //Add elements to a new ArrayList
                }
                i >>= 1;
                index++;
            }
            allsubsets.add(subset);
        }
        return allsubsets;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ArrayList<Integer> set = new ArrayList<Integer>(); //Create an ArrayList
        set.add(1);
        set.add(2);

        System.out.println(getSubsets2(set));
    }
}

结果应为[[],[1],[2],[1,2]]

但是我无法得到结果，异常如下:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

Answer 1

您的 while 循环不正确。

使用 for 循环变得更加简洁:

import java.util.ArrayList;

public class Subset { //Generate all subsets by generating all binary numbers
    public static ArrayList<ArrayList<Integer>> getSubsets2(ArrayList<Integer> set) {

        ArrayList<ArrayList<Integer>> allsubsets =
        new ArrayList<ArrayList<Integer>>();
        int max = 1 << set.size();             //there are 2 power n different subsets

        for (int i = 0; i < max; i++) {
            ArrayList<Integer> subset = new ArrayList<Integer>();
            for (int j = 0; j < set.size(); j++) {
                if (((i >> j) & 1) == 1) {
                    subset.add(set.get(j));
                }
            }
            allsubsets.add(subset);
        }
        return allsubsets;
    }

    public static void main(String[] args) {
        ArrayList<Integer> set = new ArrayList<Integer>(); //Create an ArrayList
        set.add(1);
        set.add(2);

        System.out.println(getSubsets2(set));
    }
}

请记住，子集运算是指数运算，因此您将获得大量元素。上面的实现仅适用于大约 32 个输入元素，因为这会产生 2^32 个输出子集，这很容易超出数组的限制...