幂集题目

编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。

说明：所谓幂集（Power Set）， 就是原集合中所有的子集（包括全集和空集）构成的集族。解集不能包含重复的子集。

幂集简析

一个有n个元素的集合{a1, a2, a3......, an-1, an}有多少个子集呢？

生成任意一个子集时，对于a1有两种选择：存在于该子集或不存在于该子集。同理a2、a3、a4......、an-1 、an都有两种选择。因此，总子集数为：2*2*2......=2?。

• 条件：n = 0

集合只有一个空子集：{}。

• 条件：n = 1

集合{a1}有2个子集：{}、{a1}。

• 条件：n = 2

集合{a1, a2}有4个子集：{}、{a1}、{a2}、{a1, a2}。

• 条件：n = 3

集合{a1, a2, a3}有8个子集:

观察上图，我们可以归纳出幂集(n-1)和幂集(n)的区别。幂集(n)的子集有两部分组成：

1. 幂集(n-1)的所有子集。
2. 幂集(n-1)的每个子集加上an。

代码及测试

public class PowerSet {
    public static List<List<Integer>> collect(List<Integer> oriSet){
        List<List<Integer>> result = new ArrayList<>();

        //Add the null sub set
        result.add(new ArrayList<>());

        for (Integer item: oriSet){
            //Combine the existed sub set with the new item
            List<List<Integer>> temp = new ArrayList<>();
            for (List<Integer> set: result){
                List<Integer> addCurrItem = new ArrayList<>(set);
                addCurrItem.add(item);
                temp.add(addCurrItem);
            }

            //Keep existed sets and add new combined sub sets
            result.addAll(temp);
        }
        return result;
    }

    public static void main(String[] args) {
        List<Integer> oriSet = new ArrayList<>();
        for (int i = 1; i <= 4; i++) {
            oriSet.add(i);
        }

        List<List<Integer>> result = PowerSet.collect(oriSet);
        for (List<Integer> set: result )
            System.out.println(set.toString());
    }
}