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

Question

这与这个问题不同：找到总和为特定值的所有子集 ，因为我不仅需要count子集的总数，还需要存储所有子集并返回它。

我编写了一个简单的（指数）算法，可以找到总和达到特定目标的子集：

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, '' )

我希望可以通过记忆来优化这一点。但我很难弄清楚这个函数的状态应该是什么（应该是nand吗target？..但我没有看到它被重复）

Answer 1

“我不认为这种情况会重演。”

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