子集和與一個整數相等算法_背包問題的一個變體：如何解決Java中的分區相等子集和問題...

子集和與一個整數相等算法

by Fabian Terh

由Fabian Terh

Previously, I wrote about solving the Knapsack Problem (KP) with dynamic programming. You can read about it here.

之前，我寫過有關使用動態編程解決背包問題(KP)的文章。你可以在這里閱讀。

Today I want to discuss a variation of KP: the partition equal subset sum problem. 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 Leetcode problem.

有關完整的問題說明(包括約束和示例)，請查看Leetcode問題。

動態編程 (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 (可達到)：

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 。
The current element is exactly the sum we want to attain. This is also trivially true. Let’s call this isExactMatch.
當前元素正是我們想要獲得的總和。這一點也是正確的。我們將此isExactMatch 。
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一樣，我們希望從下至上逐步構建表格。我們從基本案例開始，直到得出最終解決方案。