Leetcode:Subsets 求數組的所有子集

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 = <code>[1,2,3]</code>, a solution

is:

本文總結了三種思路來求數組的子集集合。前兩種思路雖然都基于遞歸，但是出發點略有不同；後一種思路基于位運算，但是對于原數組的數量有限制。

1.基于dfs的遞歸

原數組中每一個元素在子集中有兩種狀态：要麼存在、要麼不存在。這樣構造子集的過程中每個元素就有兩種選擇方法：選擇、不選擇，是以可以構造一顆二叉樹來表示所有的選擇狀态：二叉樹中的第i+1層第0層無節點表示子集中加入或不加入第i個元素，左子樹表示加入，右子樹表示不加入。所有葉節點即為所求子集。是以可以采用dfs的遞歸思想求得所有葉節點。

代碼如下：

2.基于同質的遞歸

隻要我們能找到比原問題規模小卻同質的問題，都可以用遞歸解決。比如要求{1,

2, 3}的所有子集，可以先求{2, 3}的所有子集，{2, 3}的子集同時也是{1, 2, 3} 的子集，然後我們把{2, 3}的所有子集都加上元素1後（注意排序），又得到同樣數量的子集， 它們也是{1, 2, 3}的子集。這樣一來，我們就可以通過求{2, 3}的所有子集來求 {1, 2, 3}的所有子集了。即為求1,2,3的子集，要先求2,3的子集，然後再把1加入到2,3的子集中去，典型的遞歸思路。代碼如下：

3.位運算

求子集問題就是求組合問題。數組中的n個數可以用n個二進制位表示，當某一位為1表示選擇對應的數，為0表示不選擇對應的數。