题目描述

求一个集合的所有结合，例如集合{A,B,C}的所有子集为：{},{A,B,C},{A,B},{A,C},{B,C},{A},{B},{C}。

思路

实际上求子集问题是一个经典的DFS，每一次选择某个元素时，都会面临两个选择，一个是不选一个是选：

第一步：选择A元素，有两种选择，一个是选A，另一个是不选A

第二步，选择B，还是有两种选择

第三步：选择C，同样有两种选择

此时最下面一排就是我们得到的所有子集。

代码实现

上面画的图实际上就是一颗递归树。

/**
 * 编写一个算法得到一个集合的所有子集
 */
public class Main {

    public static void main(String[] args) {
        int[] arr = {1, 2};
        Set<Set<Integer>> f = f(arr.length, arr);
        System.out.println(f);
    }

    /**
     *
     * @param k   这一波需要加入的第几号元素
     * @param arr
     * @return
     */
    public static Set<Set<Integer>> f(int k, int[] arr) {
        if (k == 0) {
            Set<Set<Integer>> set = new HashSet<>();
            set.add(new HashSet<>());//添加一个空集合
            return set;
        }

        Set<Set<Integer>> set = f(k - 1, arr);
        Set<Set<Integer>> resultSet = new HashSet<>();

        for (Set<Integer> integerSet : set) {//扫描上一层的集合

            //上一层的每个集合都包含两种情况，一种是加入新来的元素，另一种是不加入新的元素
            HashSet<Integer> subSet = new HashSet<>();

            subSet.addAll(integerSet);
            subSet.add(arr[k - 1]);

            resultSet.add(subSet);
            resultSet.add(integerSet);
        }
        return resultSet;
    }
}

最后

以上就是美丽大碗为你收集整理的求一个集合的所有子集题目描述思路代码实现的全部内容，希望文章能够帮你解决求一个集合的所有子集题目描述思路代码实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。