Python子集总和

Question

我正在尝试编写一个函数,该函数不仅可以确定集合子集的总和是否会添加到所需的目标编号,还可以打印作为解决方案的子集.

这是我的代码,用于查找是否存在子集:

def subsetsum(array,num):

    if num == 0 or num < 1:
        return False
    elif len(array) == 0:
        return False
    else:
        if array[0] == num:
            return True
        else:
            return subsetsum(array[1:],(num - array[0])) or subsetsum(array[1:],num)

如何修改它以记录子集本身,以便我可以打印它？提前致谢!

Answer 1

根据您的解决方案:

def subsetsum(array,num):

    if num == 0 or num < 1:
        return None
    elif len(array) == 0:
        return None
    else:
        if array[0] == num:
            return [array[0]]
        else:
            with_v = subsetsum(array[1:],(num - array[0])) 
            if with_v:
                return [array[0]] + with_v
            else:
                return subsetsum(array[1:],num)

Answer 2

您可以更改方法以更轻松地执行此操作,例如:

def subsetsum(array, num):
    if sum(array) == num:
        return array
    if len(array) > 1:
        for subset in (array[:-1], array[1:]):
            result = subsetsum(subset, num)
            if result is not None:
                return result

这将返回有效的子集或None.

Answer 3

Samy 的答案的稍微修改版本以打印所有可能的组合。

def subset(array, num):
    result = []
    def find(arr, num, path=()):
        if not arr:
            return
        if arr[0] == num:
            result.append(path + (arr[0],))
        else:
            find(arr[1:], num - arr[0], path + (arr[0],))
            find(arr[1:], num, path)
    find(array, num)
    return result

Answer 4

我想我会加入另一种解决方案。

我们可以将列表子集的每个选择映射到一个（以 0 填充的）二进制数，其中 0 表示不选取列表中相应位置的成员，1 表示选取该成员。

因此，屏蔽[1, 2, 3, 4]with0101创建了子列表[2, 4]。

因此，通过生成 0 到 2^LENGTH_OF_LIST 范围内的所有以 0 填充的二进制数，我们可以迭代所有选择。如果我们使用这些子列表选择作为掩码并对选择求和 - 我们就可以知道答案。

它是这样完成的：

#!/usr/bin/env python

# use a binary number (represented as string) as a mask
def mask(lst, m):
    # pad number to create a valid selection mask 
    # according to definition in the solution laid out 
    m = m.zfill(len(lst))
    return map(lambda x: x[0], filter(lambda x: x[1] != '0', zip(lst, m)))

def subset_sum(lst, target):
    # there are 2^n binary numbers with length of the original list
    for i in xrange(2**len(lst)):
        # create the pick corresponsing to current number
        pick = mask(lst, bin(i)[2:])
        if sum(pick) == target:
            return pick
    return False


print subset_sum([1,2,3,4,5], 7)

输出：

[3, 4]

要返回所有可能性，我们可以使用生成器来代替（唯一的变化是subset_sum，使用yield代替return和删除return False防护）：

#!/usr/bin/env python

# use a binary number (represented as string) as a mask
def mask(lst, m):
    # pad number to create a valid selection mask 
    # according to definition in the solution laid out 
    m = m.zfill(len(lst))
    return map(lambda x: x[0], filter(lambda x: x[1] != '0', zip(lst, m)))

def subset_sum(lst, target):
    # there are 2^n binary numbers with length of the original list
    for i in xrange(2**len(lst)):
        # create the pick corresponsing to current number
        pick = mask(lst, bin(i)[2:])
        if sum(pick) == target:
            yield pick

# use 'list' to unpack the generator
print list(subset_sum([1,2,3,4,5], 7))

输出：

[[3, 4], [2, 5], [1, 2, 4]]

注意：虽然不用零填充掩码也可能有效，因为它只会以相反的顺序选择原始列表的成员 - 我没有检查它也没有使用它。

我没有使用它，因为（对我来说）这种类似三元组的掩码（1、0 或什么都没有）不太明显，而且我宁愿把一切都定义清楚。