获取所有子集使其和为s的Python程序

在Python中，我们可以通过编写简单易懂的代码来获取特定和的所有子集。总体来说，我们将构建一个函数，该函数将一个数字列表作为输入，并返回所有和为s的子集。这里，我们将使用两个方法，一个是递归方法，另一个是迭代方法。

递归方法

递归方法是在本方法之前为您提供实现的一种方法。以下是实现代码-

def solve(arr, s):
    def helper(arr, s, res, path):
        if not arr and s == 0:
            res.append(path)
            return
        if not arr:
            return
        helper(arr[1:], s, res, path)
        helper(arr[1:], s - arr[0], res, path + [arr[0]])

    res = []
    helper(arr, s, res, [])
    return res

在这段代码中，首先将测试数组传递到函数中。接下来，我们定义了一个 helper() 函数，该函数用于获取子集。由于我们希望在运行时启动递归，因此将其包含在函数内部中。现在秘诀来了，当我们将数组划分为两个子数组时，每个子数组都代表一个包含或不包含当前数字的情况，而递归堆栈通过子数组来处理这些情况。每次处理当前数字时，将其添加到 path 中，并将其传入递归函数中。我们递归处理当前数字时，会将其从子数组中除去，因此我们最终可以获取所有子集。

最后一个步骤是将数组和指定和的总和传递到 solve() 函数中，该函数将运行我们的算法并返回结果。函数运行时传递的参数为arr=[2,3,4,5,6]和s=8，以下是输出结果:

[[2, 3, 3], [2, 6], [3, 5], [8]]

这个结果展示了可行的和为8子集的所有组合。

迭代方法

现在让我们尝试一下另一种方法，使用迭代方法来获取和为s的所有子集：

def subset_sum(arr, s):
    n = len(arr)
    dp = [[[] for j in range(s+1)] for i in range(n+1)]
    for i in range(n+1):
        dp[i][0] = [[]]
    for i in range(1,n+1):
        for j in range(1,s+1):
            if j < arr[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                for lst in dp[i-1][j-arr[i-1]]:
                    dp[i][j].append(lst + [arr[i-1]])
                dp[i][j] += dp[i-1][j]
    return dp[n][s]

在这段代码中，我们创建了一个 dp 数组，这里将存储所有子数组的总和并转换。在处理前，我们将其二维数组作为列表数组创建，并将其全部设置为空列表（[]）。首先，我们将最初的边界设为 [[]]，这意味着只有一个元素时元素的总和为零。

接下来，我们开始填充 dp 数组，我们这里创建了两个嵌套的循环，用于迭代处理 dp 数组，其中 i 表示当前正在处理的数字（从头开始），j 表示正在计算什么总和。在这些循环内部，我们开始逐步地填充列表数组，该列表数组将包含所有子集合，其和为 s。若当前处理的数字小于总和，则我们只需将上一个位置处的列表添加到当前位置处即可(dp[i][j] = dp[i-1][j])，否则，我们需要将可能的子数组和当前数字合并，这样才能得到更大的和。为此，我们使用第二个循环来迭代处理上一个数字的列表数组并添加到当前数字处理中的列表中，以便得到组合。之后，将上一个元素位置处的所有内容复制到当前位置中，以便我们能够使用已计算的子集。

最后，我们将 dp[n][s]返回，即所有输入数组中，包含子数组总和为 s 的元素的子数组。该函数运行时传递的参数为 arr=[2,3,4,5,6]和s=8。以下是输出结果：