1 生成子集

1.1 含義

給定一個集合，枚舉它所有可能的子集。

比如給定集合｛1，2，3｝，應該輸出：

{}

{1}

{2}

{1, 2}

{3}

{1, 3}

{2, 3}

{1, 2, 3}

1.2 增量構(gòu)造法

增量構(gòu)造法，每次選擇一個元素放到集合中，每次操作的結(jié)果即是一個子集。

遞歸操作，每次向當前集合中添加一個比當前集合中最大的元素大1的數(shù)。

代碼：

[python]?view plain?copy

from?__future__?import?print_function??

??

def?print_subset(n,?lst,?cur):??

????for?i?in?range(cur):??

????????print(lst[i]+1,?end='')??

????print()??

????if?cur:??

????????s?=?lst[cur?-?1]?+?1??

????else:??

????????s?=?0??

????for?i?in?range(s,?n):??

????????lst[cur]?=?i??

????????print_subset1(n,?lst,?cur+1)??

1.3 位向量法

構(gòu)造位向量（可理解為構(gòu)造一個數(shù)組），該向量中的每一位置可以取0值或者1值，0和1分別代表該位置上對應的值是否在集合中。如向量為[1, 0, 0, 1]，其第1和4位上有1，所以該向量表示的集合為{1, 4}。

思路：
如果需要用向量來表示集合，那么需要保證向量的每一種變化能夠剛好覆蓋集合的每一種可能性。

對n求子集，構(gòu)造長度為n的向量，每一位可以代表取或者不取該位置的值，共有2^n中可能。

代碼為：
[python]?view plain?copy

from?__future__?import?print_function??

??

def?print_subset(n,?lst,?cur):??

????if?cur?==?n:??

????????for?i?in?range(n):??

????????????if?lst[i]:??

????????????????print(i+1,?end='')??

????????print()??

????else:??

????????lst[cur]?=?0??

????????print_subset(n,?lst,?cur+1)??

????????lst[cur]?=?1??

????????print_subset(n,?lst,?cur+1)??

1.4?二進制法

我們可以使用二進制法來表示子集。對于n求子集，其子集有2^n個（包括空集），比如n = 4，其有16個子集，這16個子集用二進制可以表示成：

0->0000->{}
1->0001->{1}
2->0010->{2}
3->0011->{1,2}
4->0100->{3}
5->0101->{1,3}
...

15->1111->{1,2,3,4}

思路：

求n的子集，可以依次處理1到2^n - 1之間的每一個數(shù)，每個數(shù)取出它二進制表示中的1的位置，以此表示該數(shù)對應的集合。比如5，二進制表示的后四位為0101，其在第1和第3位處有1，那么，其代表的集合為{1, 3}。使用位運算中與（&）操作，可以方便的求出二進制某位置上是否為1。

代碼：
[python]?view plain?copy

from?__future__?import?print_function??

s?=?1??

n?=?4??

while?s?<?(1?<<?n):??#?依次遍歷1到2^n?-?1之間的每一個數(shù)??

????for?i?in?range(n):??#?每一個數(shù)使用&操作判斷該位置上是否有1，有打印或者保存起來??

????????if?s?&?(1?<<?i):??

????????????print(i+1,?end='')??

????print()??

????s?+=?1??

總結(jié)

以上是生活随笔為你收集整理的面试编程题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。