子集和问题
给定一个整数集，是否存在子集使和为0
例：[-7,-3,2,5,8]中存在[-7,2,5]和为0
暴力解法，求出所有的子集，判断是否为0
子集的个数：因为每一个元素要么出现要么不出现，所有一共有2^n个
先假设A中只有三个元素，元素出现用1表示不出现用0表示
所有子集为[100], [010], [001], [110], [101], [011], [111], [000]，每个子集也可用十进制表示
同理，可以 10进制转换为2进制，再找到相对应的子集
代码实现
def subset_sum(lst, target): for i in range(1, 2**len(lst)): pick = list(mask(lst, bin(i)[2:]))# 找到所有子集 if sum(pick) == target: yield pick def mask(lst, m): ''' 取得lst中对应位置的元素 ''' m = m.zfill(len(lst)）# 增加长度，不够补0 res = [] for i in range(len(lst)): if m[i] != '0': res.append(lst[i]) return res # 高级写法 # return map(lambda x: x[0], filter(lambda x: x[1] != '0', zip(lst, m))) result = subset_sum([1, 2, 3], 5) for i in result: print(i)时间复杂度o(2^n)，指数级，当n>1000时，单位为年
