leetcode上一道很经典的问题
#题目:
Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
先介绍两种非递归的写法
#method 1
从上面的二叉树可以观察到,当前层的集合 = 上一层的集合 + 上一层的集合加入当前层处理的元素得到的所有集合(其中树根是空集),因此可以从第二层开始(第一层是空集合)迭代地求最后一层的所有集合(即叶子节点)
#method 2
由于S[0: n-1]组成的每一个subset,
可以看成是对是否包含S[i]的取舍。
S[i]只有两种状态,包含在特定subset内,或不包含。
所以subset的数量总共有2^n个。所以可以用0~2^n-1的二进制来表示一个subset。
二进制中每个0/1表示该位置的S[i]是否包括在当前subset中。
接下来采用两种递归的方式来遍历数组
#method 3
采用dfs递归的方式 与二叉树的遍历很像
求集合的所有子集问题。题目要求子集中元素非递减序排列,因此我们先要对原来的集合进行排序。原集合中每一个元素在子集中有两种状态:要么存在、要么不存在。这样构造子集的过程中每个元素就有两种选择方法:选择、不选择,因此可以构造一颗二叉树,例如对于例子中给的集合[1,2,3],构造的二叉树如下(左子树表示选择该层处理的元素,右子树不选择),最后得到的叶子节点就是子集
;
#method 4
采用回溯递归的方式,有时可以剪枝处理
首先我们需要对集合排序,对于一个n元素的集合,首先我们取第一个元素,加入子集合中,后面的n - 1个元素可以认为是第一个元素的子节点,我们依次遍历,譬如遍历到第二个元素的时候,后续的n - 2个元素又是第二个元素的子节点,再依次遍历处理,直到最后一个元素,然后回溯,继续处理。处理完第一个元素之后,我们按照同样的方式处理第二个元素。
;