关于一个集合的子集的思考

之前做过很多类似的题目，比如说给你一个字符串ABC，然后请给出他的子集（A，B，C，AB，AC，BC，ABC），差不多都是这样的，当然也有给你ABC，请给出跟其长度一样的组合（ABC,ACB,BAC,BCA,CAB,CBA）等等。由于这种题目都是涉及到排列组合数学，因此这里来总结一下。

1.首先我们来讨论第一种情况，即给出一个集合，求出其子集。

从数学角度，我们可以知道，拥有n个元素的集合，它拥有 2n 个子集（包含空集的情况），因此我们的复杂度不可能会低于 2n 。

下面我们使用递归的方法来求。

• 终止条件：n = 0；

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

• 情况：n = 1 ;

集合{ a1 }有2个子集：{ }和{ a1 }.

• 情况：n = 2;

集合{ a1 ， a2 }有四个子集：{ }，{ a1 }，{ a2 }，{ a1 ， a2 }。

从上面我们继续往下推断，我们应该如何使用p（2）来构造p（3）？

答案是复制p（2），并在这些子集中添加 a3 ，然后再将p（2）与其合并，即可产生p（3）；

下面是实现上述思路的代码：

    public ArrayList<ArrayList<Integer>> getR(ArrayList<Integer> set, int index)
    {

        ArrayList<ArrayList<Integer>> allsubsets;
        if (set.size() == index)
        {// 终止条件
            allsubsets = new ArrayList<ArrayList<Integer>>();
            allsubsets.add(new ArrayList<Integer>());
        } else
        {
            allsubsets = getR(set, index + 1);

            int item = set.get(index);

            ArrayList<ArrayList<Integer>> biggersubsets = new ArrayList<ArrayList<Integer>>();// 存储p(3)

            for (ArrayList<Integer> subset : allsubsets)// subset是p(2)的一个子串（子串是用list表示的）
            {

                ArrayList<Integer> newlist = new ArrayList<>();// 不能覆盖p(2),因此需要重新起一个子串并在这些子串上操作
                newlist.addAll(subset);
                newlist.add(item);// 每个子串都添加a3
                biggersubsets.add(newlist);// 子串加入p(3)
            }
            allsubsets.addAll(biggersubsets);// p(3)加入总结果
        }

        return allsubsets;

    }

另外一种思路是，每个元素在子集中的出现都是2种情况，有或者没有这种元素，因此我们构造0- 2n−1 个连续的二进制数，用他们每一位的表示来标识元素出现的情况。

下面是代码：

    public ArrayList<ArrayList<Integer>> getSub(ArrayList<Integer> set)
    {

        ArrayList<ArrayList<Integer>> allsubsets = new ArrayList<ArrayList<Integer>>();

        int max = 1 << set.size();

        for (int k = 0; k < max; k++)
        {
            ArrayList<Integer> subset = convertIntToset(k, set);// 将k代表的二进制数化为子集。
            allsubsets.add(subset);
        }

        return allsubsets;
    }

    public ArrayList<Integer> convertIntToset(int x, ArrayList<Integer> set)
    {

        ArrayList<Integer> subset = new ArrayList<>();
        int index = 0;
        for (int k = x; k > 0; k >>= 1)
        {
            if ((k & 1) == 1)// 取最后一位
            {
                subset.add(set.get(index));
            }
            index++;
        }

        return subset;

    }

第二种情况是不求子集，而是求组合的情况。

详细见我的这篇博客