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

稍微更新了一下下面的代码，以便返回这个问题的所有可能组合。上面讨论中的代码在输入为subset([4,3,1],4)时不会打印出所有可能的组合。

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 2

我想再提供一个解决方案。

我们可以把列表中每个子集的选择映射成一个（用0填充的）二进制数字，其中0表示不选这个位置的成员，1表示选这个位置的成员。

比如，用 0101 来处理 [1, 2, 3, 4]，就会得到子列表 [2, 4]。

因此，通过生成从0到2的列表长度次方的所有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或什么都没有）不太明显，我更喜欢一切都清晰明了。

Answer 3

你可以换个方法来更简单地做到这一点，比如这样：

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 4

修改代码，让它在找到匹配的时候也能检测重复项，并提供更多的解决方案。

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 5

根据你的解决方案：

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)