LeetCode--subsets

2018-01-22 10:43:24来源:网络收集作者:咖啡不加糖人点击

分享

[var1]
题目描述



Given a set of distinct integers, S, return all possible subsets.



Note:


Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets.



For example,
If S =[1,2,3], a solution is:


[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
分析:递归的解法,相当于一种深度优先搜索,参见网友JustDoIt的博客,由于原集合每一个数字只有两种状态,要么存在,要么不存在,那么在构造子集时就有选择和不选择两种情况,所以可以构造一棵二叉树,左子树表示选择该层处理的节点,右子树表示不选择,最终的叶节点就是所有子集合,树的结构如下:                       []        
                   /          /        
                  /            /     
                 /              /
              [1]                []
           /       /           /    /
          /         /         /      /        
       [1 2]       [1]       [2]     []
      /     /     /   /     /   /    / /
  [1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台