DFS 算法详解：求解数组子集问题

3.本期要讲解的题目是

子集

要点：

• nums 元素各异
• 要返回空集

4.解题

本题我们可以画出两种决策树。

4.1 决策树 1

高中，我们学集合的时候知道，一个集合的子集个数为 2^n 个。这个 2^n 怎么来的？

在一个元素对于集合来说，只有两种情况：存在或者不存在。

对于每一个元素进行存在或者不存在的划分，我们可以得出以下的决策图：

我们发现决策树的结果完全符合我们的期望，所以这就是一个好的决策树。

有了决策树，根据其写代码就方便多啦~

根据决策树，我们得出需要

两个全局变量：

• 上一级已经存放了的元素–>变量path（也可以设置成函数参数，避免返回现场操作）
• 存放 path 的二维数组用于返回所有结果–>ret

父子层信息传递需要：

• 数组–>nums
• 这一层是对数组中第几个元素进行判断–>pos

代码逻辑

观察我们想要的结果，都是在叶子结点，很明显，

出口在叶子节点

重复子问题：对于每个元素根据其是否存在，分两种情况讨论 子问题干啥：存在则将其放入 path 中，进入下一层，不存在啥也不做，进入下一层

4.2 决策树 2

我们也可以根据，子集中元素的个数，来画决策图：

这张决策图同样需要全局变量 path 和 ret，它也能获得我们想要的结果，也是一个好的决策图。

由于子集中没有排序，只有组合，所以我们要对重复的子集进行剪枝，如图中所示：按照顺序来给 path 添加元素。

提示： 结合 for 循环，不用设置 return 出口，for 循环能实现数组递归中的按下标顺序添加元素，进行剪枝，出口的本质是：'没有可选择元素'。

不知道大家有没有发现，数组往往是多叉树的遍历，多叉树的遍历必然用到 for，而 for 往往是遍历到最后，也就不需要设置 return 出口~

5.下期要讲解的题目是：

找出所有子集的异或总和再求和