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();
        }
    }

2.分析

时间复杂度：O()

空间复杂度：O(n)

????????