python - 我怎样才能记住这个子集和算法？

Question

这与这个问题不同:find all subsets that sum to a particular value因为我不仅需要计算子集的总数，还需要存储所有子集并返回它。

我写了一个简单的(指数)算法来找到总和达到特定目标的子集:

Eg:
arr = [1,2,3,4,5,6,7,8]
Possible subsets:
5
4,1
3,2

这是我的算法

n -> 列表索引(从末尾开始)

目标 -> 我要创建的子集的总和

arr = [1,2,3,4,5,6,7,8]
def subset_sum(arr, n, target, result):

    if target == 0:
        print result
        return

    if target < 0 or n < 0:
        return False



    subset_sum(arr, n-1, target - arr[n], result + str(arr[n]))
    subset_sum(arr, n - 1, target, result)

print subset_sum(arr, len(arr) - 1, 5, '' )

我想优化这一点，可能是通过内存。但是我很难弄清楚这个函数的状态应该是什么(它应该是 n 和 target 吗？..但我没有看到它被重复)

Answer 1

"I don't see it being repeated."

考虑一个具有重复值或零的数组的简单示例。
例如arr = [3,2,4,5,0,5]，您正在寻找总和为 7 的子集，请参阅此处，索引 3(如果起始索引为 1)被结果 2 击中两次，一次是最后 5 个包含在答案中，当它被排除在答案之外时再次出现
为了更清楚，请在此处查看另一个示例
arr = [5,2,3,6,3,5,8]，您正在寻找总和 12，您选择最后一个索引，即 7，然后留下 6,5，从而以总和 4 到达索引 4，或者您离开索引7 并选择索引 6,5 并再次以总和 4 达到索引 4。
所以这里需要内存。
您还可以通过构建 n 行和列求和的矩阵，以自下而上的方式解决问题，反之亦然。