面试算法79:所有子集

2024-01-02 12:31:40

题目

输入一个不含重复数字的数据集合,请找出它的所有子集。例如,数据集合[1,2]有4个子集,分别是[]、[1]、[2]和[1,2]。

分析

如果集合中包含n个元素,那么生成子集可以分为n步,每一步从集合中取出一个数字,此时面临两个选择,将该数字添加到子集中或不将该数字添加到子集中。生成一个子集可以分为若干步,并且每一步都面临若干选择,这正是应用回溯法的典型场景。

public class Test {
    public static void main(String[] args) {
        int[] nums = {1, 2};
        List<List<Integer>> result = subsets(nums);
        for (List<Integer> item : result) {
            System.out.println(item);
        }
    }

    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        if (nums.length == 0) {
            return result;
        }

        helper(nums, 0, new LinkedList<Integer>(), result);
        return result;
    }

    private static void helper(int[] nums, int index, LinkedList<Integer> subset, List<List<Integer>> result) {
        if (index == nums.length) {
            result.add(new LinkedList<>(subset));
        }
        else if (index < nums.length) {
            helper(nums, index + 1, subset, result);// 直接不添加元素

            subset.add(nums[index]);// 添加元素
            helper(nums, index + 1, subset, result);
            // 等递归函数执行完成之后,函数helper也执行完成,接下来将回到前一个数字的函数调用处继续执行。那么此时将回溯到父节点,以便尝试父节点的其他选项。
            // 在回溯到父节点之前,应该清除已经对子集状态进行的修改。此前在子集subset中添加了一个数字,此时应该将它删除。
            subset.removeLast();
        }
    }
}

文章来源:https://blog.csdn.net/GoGleTech/article/details/135336396
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。