编写 Python 程序查找完美和

在本教程中，我们将编写 Python 程序来查找给定列表中的完美和。让我们先理解问题陈述。

问题陈述

给定一个由非负整数组成的数组 arr[] 和一个整数 sum，任务是计算给定数组中和等于给定 sum 的所有子集的数量。例如 -

示例 - 2

解决方案 -

我们可以使用递归和动态规划来解决这个问题。让我们先理解递归方法。

方法 1：使用递归

在此方法中，我们将使用递归函数，该函数将考虑给定数组的所有子集，并检查每个子集的和是否等于给定的和。我们将使用记忆化来避免重复计算。让我们理解下面的示例。

示例 -

输出

3

解释 -

在上面的代码中，我们定义了一个递归函数 `count_subsets_recursive(arr, n, sum, memo)`，其中 `arr` 是给定的数组，`n` 是数组中的元素数量，`sum` 是目标和，`memo` 是用于存储中间结果的记忆化表。

递归的基线情况是当和为 0 时。在这种情况下，我们返回 1，因为总有一个空子集，其和为 0。

如果元素数量为 0 且和不为 0，我们返回 0，因为没有子集的和等于给定的和。

对于其他情况，我们有两种选择：要么将当前元素 `arr[n-1]` 包含在子集中，要么排除它。

如果我们排除它，我们就对剩余的 n-1 个元素递归调用 `count_subsets_recursive()` 函数，即 `count_subsets_recursive(arr, n-1, sum, memo)`。

如果我们包含它，我们就对剩余的 n-1 个元素和减去当前元素后的剩余和递归调用 `count_subsets_recursive()` 函数，即 `count_subsets_recursive(arr, n-1, sum-arr[n-1], memo)`。

我们将上述两种选择的结果相加，并将结果存储在记忆化表中以避免重复计算。最后，我们返回结果。

方法 2：使用动态规划

在此方法中，我们将使用动态规划，其中我们定义一个二维数组 `dp[n+1][sum+1]`，其中 `dp[i][j]` 表示数组前 i 个元素的子集中和等于 j 的数量。

让我们来理解以下代码——

示例 -

输出

3

解释 -

在此方法中，我们创建一个大小为 (n+1) x (sum+1) 的二维数组 `dp`，其中 `n` 是数组中的元素数量，`sum` 是目标和。每个元素 `dp[i][j]` 表示数组前 i 个元素中和等于 j 的所有子集的计数。我们将数组的第一列初始化为 1，因为总有一个空子集，其和为 0。我们使用以下递归关系。

第一种情况代表当前元素 `arr[i-1]` 大于当前和 `j` 的情况。在这种情况下，我们不能将当前元素包含在任何和等于 `j` 的子集中。因此，我们只需复制 `dp[i-1][j]` 的值。

第二种情况代表当前元素 `arr[i-1]` 小于或等于当前和 `j` 的情况。在这种情况下，我们可以选择将当前元素包含在子集中，也可以选择排除它。

如果我们排除它，则和等于 `j` 的子集的计数将与从前 i-1 个元素形成的和等于 `j` 的子集的计数相同。如果我们包含它，我们需要找到从前 i-1 个元素形成的和等于 `j-arr[i-1]` 的子集的计数，因为我们已经包含了当前元素 `arr[i-1]`。

最后，我们返回 `dp[n][sum]` 的值，它表示整个数组中和等于给定和的所有子集的计数。