17. Subsets
2019-06-24 本文已影响0人
鸭蛋蛋_8441
Description
Given a set of distinct integers, return all possible subsets.
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
Example
Example 1:
Input: [0]
Output:
[
[],
[0]
]
Example 2:
Input: [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
Challenge
Can you do it in both recursively and iteratively?
思路：
1.一般求所有可能方案的都用到深度优先搜索，这个题的分析过程可以参考下图，就是每一步都有选一个数或不选一个数两种可能，一直走到最底层的就是所有的答案，注意需要deepcopy。
2.还有一种分析思路如下图， 所有的节点都是我们要的结果，每一层都要回溯去掉相应的元素：
3.用非递归的方式实现，用到了BFS，图解类似思路2。
代码：
