Leetcode 78 子集

题意理解：

求一个集合的所有子集。该集合中没有重复元素。

首先明确什么是子集：子集中的元素都在全集里。

[1,2,3]

子集：[]、[1]、[2]、[3]、[12]、[13]、[23]、[123]

注意：[]空集是所有集合的子集。

解题思路：

类似于组合、划分类问题，都可以以回溯的思路来解决。

首先可以将其抽象为树结构。

可以发现：该树的每一个节点都是一个子集。在所有节点收集结果，即可解题。

1.暴力回溯+剪枝优化

我们需要在每一个节点收集结果。根据回溯的三个步骤解题：

首先确定返回值和参数列表：其实通常返回值都是void

确定终止条件

单层递归逻辑

因为要收集的结果在所有的节点上，实际上，每进一次递归就相当于一个节点。所有每次进递归时都收集结果。

    List<List<Integer>> result=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums,0);
        return result;
    }

    public void backtracking(int[] nums,int startIndex){
        //结果收集
        result.add(new ArrayList<>(path));
        if(startIndex>=nums.length) return;
        //单层递归逻辑
        for(int i=startIndex;i<nums.length;i++){
            path.add(nums[i]);
            backtracking(nums,i+1);
            path.removeLast();
        }
    }