題目描述

有一個集合S，要求打印出其所有子集，子集元素用逗號隔開，其中集合S本身和空集NULL都認為是集合S的子集。例如，有一個集合S，它的內容為“S={"A", "B", "C"}”，那么該集合S的所有子集為“A,B,C”、“A,B”、“AC”、“BC”、“A”、“B”、“C”、“NULL”。

解題思路

先要思考如何將集合求子集這個操作與二進制聯(lián)系起來，首先可以確定，集合S、空集以及單個元素的子集很容易確定，不用與二進制關聯(lián)也可以輕松得到，剩下的子集的求解思路就是某個元素不在子集中時，剩下的所有元素為一個子集，然后依次是某兩個元素不在子集中時剩下的元素為一個子集，以此類推，就可以得到所有子集。聯(lián)想二進制的特點，一個比特位上要么是0，要么就是1，那么可以使用比特位代表每個元素，它的值為1時表示此元素在子集中，值為0時表示此元素不在子集中，然后根據(jù)“題目”中的例子，將集合S的所有子集用二進制表示出來，然后寫出對應的十進制就可以看到對應的規(guī)律了。

解題代碼

def print_sub(val, s):
    # 獲取對應位數(shù)的二進制位字符串
    bin_str = bin(val).replace('0b', '').rjust(len(s), '0')

    idx = 0
    is_null = True
    while idx < len(s):
        # 如果該比特位為1，則打印對應的元素
        if bin_str[idx] == '1':
            if not is_null:
                print(',', end='')

            is_null = False
            print(s[idx], end='')

        idx += 1

    if is_null:
        print('NULL', end='')

    print(';')


def func(s):
    # 使用二進制的方式得到所有元素都存在時的二進制表示方式對應的十進制數(shù)
    # 當然，也可以使用其他方式得到這個值
    val = 0
    for i in range(len(s)):
        val |= (1 << i)

    # 遍歷并打印每一個子集
    while val >= 0:
        print_sub(val, s)
        val -= 1


if __name__ == '__main__':
    collection = ['A', 'B', 'C', 'D']
    func(collection)

輸出：

A,B,C,D;
A,B,C;
A,B,D;
A,B;
A,C,D;
A,C;
A,D;
A;
B,C,D;
B,C;
B,D;
B;
C,D;
C;
D;
NULL;

總結

求集合的子集，在Python中itertools.combinations也可以做到，或者自己編寫另外的算法，但是就此題而言，相當于是提供了另一種解題思路或者說是二進制的一種操作方法，可以參考下。

題目及解題算法來自：書籍《Python程序員面試寶典》。