子集和问题（python）

问题描述：
（a）写出集合A=[5,-2,4,2]的所有子集。
（b）写出程序判断A是否存在一个子集使得该子集元素的和为0，并分析其时间复杂度。
先贴代码：

def subset(A:list)->list:		#求集合的所有子集
    N=len(A)					
    Subset=[]					
    for i in range(2**N):
        b=[]
        for j in range(N):
            if (i>>j)%2==1:		#关键：判断该位是否为1
                b.append(A[j])
                if b not in Subset:
                    Subset.append(b)
    return Subset

def sum_subset(S：list)->list:	#求子集和
    for i in S:
        if sum(i)==0:
            print(i)

if __name__=="__main__":
    A=[5,2,4,-2]
    S=subset(A)
    sum_subset(S)

输出[2,-2]

解析：
二进制求子集：集合元素为n，其子集的个数是2^n，而n位二进制数能表示的数也是2 ^n个，如果用二进制的每一位数都对应一个元素，这个位数为1表示集合中有相对应元素，
这个位数为0表示集合中没有相对应的元素，因此，每一个二进制数都可以与一个子集相对应。
关键为如何判断n位二进制数哪些为1，哪些为0

if (i>>j)%2==1:

如果此时i=13，其用二进制表示为：1101
j的值为0，1，2，3

• 当j=0时，判断最右边一位是否为1
  由i>>j得i右移0位，此时(i>>j)等于13（为奇数），if成立
• 当j=1时，判断右边第二位是否为1
  由i>>j得i右移1为，此时(i>>j)等于6，二进制表示为110，if不成立
  …

其实在n为二进制数中，能决定它是奇数还是偶数的只有最右边一位，如果最右边一位为1，则必为奇数（2^0=1），如果为0，则为偶数
所以我们只要先判断最右边一位是否为1，也就是该数是否为奇数，然后右移该数一位，继续判断右边第二位是否为1，如此反复直至全部判断完。