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)

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

原文由 Chase McCoy 发布，翻译遵循 CC BY-SA 4.0 许可协议

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)

原文由 Samy Arous 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

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

原文由 harry 发布，翻译遵循 CC BY-SA 3.0 许可协议