子集和与一个整数相等算法

by Fabian Terh

由Fabian Terh

Previously, I wrote about solving the Knapsack Problem (KP) with dynamic programming. .

之前，我写过有关使用动态编程解决背包问题(KP)的文章。 。

Today I want to discuss a variation of KP: the . I first saw this problem on Leetcode — this was what prompted me to learn about, and write about, KP.

今天，我要讨论KP的一种变体： 。 我首先在Leetcode上看到了这个问题-这就是促使我学习和撰写KP的原因。

This is the problem statement (reproduced partially without examples):

这是问题说明(部分复制而没有示例)：

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

给定一个仅包含正整数的非空数组，请确定该数组是否可以划分为两个子集，以使两个子集中的元素之和相等。

For the full problem statement, with constraints and examples, check out the .

有关完整的问题说明(包括约束和示例)，请查看 。

动态编程 (Dynamic programming)

Like with KP, we’ll be solving this using dynamic programming. Since this is a variation of KP, the logic and methodology is largely similar.

与KP一样，我们将使用动态编程来解决此问题。 由于这是KP的变体，因此逻辑和方法学非常相似。

解 (Solution)

We will house our solution in a method that returns a boolean — true if the array can be partitioned into equal subsets, and false otherwise.

我们将解决方案包含在一个返回布尔值的方法中—如果可以将数组划分为相等的子集，则返回true，否则返回false。

步骤1：防止奇数数组和 (Step 1: Guarding against odd array sum)

Trivially, if all the numbers in the array add up to an odd sum, we can return false. We only proceed if the array adds up to an even sum.

琐碎地，如果数组中的所有数字加起来为奇数和，则可以返回false。 我们仅在数组加和为偶数时继续进行。

步骤2：建立表格 (Step 2: Creating the table)

Next, we create the table.

接下来，我们创建表。

Table rows represent the set of array elements to be considered, while table columns indicate the sum we want to arrive at. Table values are simply boolean values, indicating whether a sum (column) can be arrived at with a set of array elements (row).

表行表示要考虑的一组数组元素，而表列表示我们要达到的总和。 表值只是布尔值，指示是否可以通过一组数组元素(行)得出总和(列)。

Concretely, row i represents a set of array elements from indices 0 to (i-1). The reason for this offset of 1 is because row 0 represents an empty set of elements. Therefore, row 1 represents the first array element (index 0), row 2 represents the first two array elements (indices 0–1), and so on. In total, we create n + 1 rows, inclusive of 0.

具体而言，第i行代表从索引0到( i -1)的一组数组元素。 偏移量为1的原因是因为行0代表一组空元素。 因此，第1行代表第一个数组元素(索引0)，第2行代表前两个数组元素(索引0-1)，依此类推。 我们总共创建n + 1行，包括0。

We only want to know if we can sum up exactly to half the total sum of the array. So we only need to create totalSum / 2 + 1 columns, inclusive of 0.

我们只想知道是否可以精确地求和该数组总和的一半。 因此，我们只需要创建totalSum / 2 + 1列(包括0)即可。

步骤3：预先填写表格 (Step 3: Pre-filling the table)

We can immediately begin filling the entries for the base cases in our table — row 0 and column 0.

我们可以立即开始在表中填充基本案例的条目-第0行和第0列。

In the first row, every entry — except the first — must be false. Recall that the first row represents an empty set . Naturally, we are unable to arrive at any target sum — column number — except 0.

在第一行中，除第一行外，每个条目都必须为false 。 回想一下，第一行代表一个空集。 自然，我们无法得出除0以外的任何目标总数(列号)。

In the first column, every entry must be true. We can always,trivially, arrive at a target sum of 0, regardless of the set of elements we have to work with.

在第一列中，每个条目都必须为true 。 无论我们要使用什么元素集，我们总是可以轻松地达到目标总和0。

步骤4：建立表格(问题的症结) (Step 4: Building the table (the crux of the problem))

Some entry in the table at row i and column j is true (attainable) if one of the following three conditions are satisfied:

如果满足以下三个条件之一，则第i行和第j列中表中的某些条目为true (可达到)：

1. the entry at row i-1 and column j is true. Recall what the row number represents. Therefore, if we are able to attain a particular sum with a subset of the elements that we have presently, we can also attain that sum with our current set of elements — by simply not using the extra elements. This is trivial. Let’s call this prevRowIsTrue.

   第i -1行和第j列的条目为true 。 回忆一下行号代表什么。 因此，如果我们能够使用当前元素的一个子集获得一个特定的总和，那么我们也可以使用我们当前的元素集来获得该总和-只需不使用额外的元素即可。 这是微不足道的。 我们将此prevRowIsTrue 。

2. The current element is exactly the sum we want to attain. This is also trivially true. Let’s call this isExactMatch.

   当前元素正是我们想要获得的总和。 这一点也是正确的。 我们将此isExactMatch 。

3. If the above two conditions are not satisfied, we have one remaining way of attaining our target sum. Here, we use the current element — the additional element in the set of elements in our current row compared to the set of elements in the previous row — and check that we are able to attain the remainder of the target sum. Let’s call this canArriveAtSum.

   如果不满足上述两个条件，则我们还有另一种方法来达到目标​​总和。 在这里，我们使用当前元素(当前行元素集中的上一个元素与前一行元素集相比的其他元素)，并检查是否能够达到目标总和的其余部分。 我们将此canArriveAtSum 。

Let’s unpack condition 3. We can only use the current element if it is less than our target sum. If they’re equal, condition 2 would be satisfied. If it’s larger, we can’t use it. Therefore, the first step is to ensure that current element < target sum.

让我们解压缩条件3。 如果当前元素小于目标总和，我们只能使用它。 如果它们相等，则将满足条件2。 如果更大，我们将无法使用。 因此，第一步是确保当前元素<目标总和。

After using our current element, we are left with the remainder of our target sum. We then check if that is attainable by checking the corresponding entry in the row above.

使用完当前元素后，剩下剩下的目标总和。 然后，我们通过检查上一行中的相应条目来检查是否可以实现。

As with regular KP, we want to progressively build our table from the bottom-up. We start with the base cases, until we arrive at our final solution.

与常规KP一样，我们希望从下至上逐步构建表格。 我们从基本案例开始，直到得出最终解决方案。

步骤5：返回答案 (Step 5: Returning the answer)

We simply return return mat[nums.length][totalSum / 2].

我们只返回return mat[nums.length][totalSum / 2] 。

工作代码 (Working code)

Thanks for reading!

谢谢阅读！

翻译自:

子集和与一个整数相等算法