這道題主要涉及的是動態規劃，類似揹包問題，主要還是需要找出狀態轉移方程，優化時可以考慮採用深度優先搜索。
原題
給定一個只包含正整數的非空數組。是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。
注意:
- 每個數組中的元素不會超過 100
- 數組的大小不會超過 200
示例 1:
<code>輸入: [1, 5, 11, 5]輸出: true解釋: 數組可以分割成 [1, 5, 5] 和 [11].```示例2:/<code>
輸入: [1, 2, 3, 5]
輸出: false
解釋: 數組不能分割成兩個元素和相等的子集.
<code>原題url：https://leetcode-cn.com/problems/partition-equal-subset-sum/## 解題### 動態規劃針對這種問題，動態規劃是最直接的思路。針對每一個數字，你都有兩個選擇：選、不選。我們的目標是為了讓選出來的數字之和等於所有數字之和的一半。這和`0-1 揹包問題`很類似，我們可以利用二維表格 dp 解決，表格有`len`行、`target+1`列，這裡`len`表示當前數字所處的數組下標，`target`表示所有數字之和(最大值為：所有數字之和的一半)，`target+1`是表明數字之和從0開始。接下來考慮`狀態定義`和`狀態轉移方程`：狀態定義：`dp[i][j]`表示從原始數組的 [0, i] 這個子區間內挑選一些數，每個數只能用一次，使得這些數的和恰好等於 j。狀態轉移方程：對於“0-1 揹包問題”，就是考慮數字是否選擇。1. 不選擇 nums[i]，如果在 [0, i - 1] 這個子區間內已經有一部分元素，使得它們的和為 j ，那麼 dp[i][j] = true；2. 選擇 nums[i]，如果在 [0, i - 1] 這個子區間內就得找到一部分元素，使得它們的和為 j - nums[i]，那麼 dp[i][j] = true；3. 其餘情況，dp[i][j] = false；所以狀態轉移方程是：`dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]`接下來我們看看代碼：/<code>
public class Solution {
<code> public boolean canPartition(int[] nums) { int len = nums.length; if (len == 0) { return false; }/<code><code> // 求所有數字之和 int sum = 0; for (int num : nums) { sum += num; }/<code><code> // 如果總和是奇數，就無法計算 if ((sum & 1) == 1) { return false; } // 目標值：總和的一半 int target = sum / 2; // 創建二維狀態數組，行：物品索引，列：容量（包括 0） boolean[][] dp = new boolean[len][target + 1];/<code><code> // 先填表格第 0 行，第 1 個數只能讓容積為它自己的揹包恰好裝滿 if (nums[0] <= target) { dp[0][nums[0]] = true; }/<code><code> // 再填表格後面幾行 for (int i = 1; i < len; i++) { for (int j = 0; j <= target; j++) { // 如果之前已經有總和為 j 的情況(這樣不需要nums[i])，說明可以滿足 if (dp[i - 1][j] || // 如果當前的數字nums[i]剛好為j，說明可以滿足 nums[i] == j || // 如果當前的數字nums[i]小於j，並且之前就有總和為(j - nums[i])的情況(這樣加上nums[i]剛好滿足j) (nums[i] < j && dp[i - 1][j - nums[i]])) { dp[i][j] = true; } else { dp[i][j] = false; } } } return dp[len - 1][target]; }}```提交OK。/<code>動態規劃——優化
時間上的優化，其實可以提前結束，只要滿足 target，就滿足了總和一半的條件，可以直接結束，並不需要全部算完。
空間上的優化，其實只需要一維即可，因為只用了上一次的所有情況，並不需要所有。
接下來我們看看代碼：
<code>public class Solution { public boolean canPartition(int[] nums) { int len = nums.length; if (len == 0) { return false; } // 求所有數字之和 int sum = 0; for (int num : nums) { sum += num; } // 如果總和是奇數，就無法計算 if ((sum & 1) == 1) { return false; } // 目標值：總和的一半 int target = sum / 2; // 創建一維數組 boolean[] dp = new boolean[target + 1]; dp[0] = true; // 記錄第一個數字的情況 if (nums[0] <= target) { dp[nums[0]] = true; } // 再填表格 for (int i = 1; i < len; i++) { for (int j = target; nums[i] <= j; j--) { if (dp[target]) { return true; } dp[j] = dp[j] || dp[j - nums[i]]; } } return dp[target]; }}/<code> 提交OK。
深度優先搜索
和動態規劃類似，只是換成了遞歸的寫法。
針對一個數字選還是不選的問題，要求選擇的數字之和達到一半，等價於不選擇的數字之和也達到了一半。
只是針對剪枝，需要提供更多一些的情況：可以先從小到大排序，然後從大的一方開始找，這樣可以快速失敗，因為當超過一半之後，可以直接結束。
接下來看看代碼：
<code>class Solution { public boolean canPartition(int[] nums) { // 求和 int sum = 0; for (int num : nums) { sum += num; } // 如果是奇數，說明不可平分 if ((sum & 1) == 1) { return false; } // 求出一半應該是多少 sum = sum >> 1; // 從小到大排序 Arrays.sort(nums); // 從後向前添加 return canPartition(nums, nums.length - 1, sum, sum); } public boolean canPartition( int[] nums, int index, int canIncrease, int canDecrease) { // 如果可以增加或者可以減少的量為0，說明已經達到一半，成功 if (canIncrease == 0 || canDecrease == 0) { return true; } // 如果可以增加或者可以減少的量為0，說明已經超過一半，失敗 if (canIncrease < 0 || canDecrease < 0) { return false; } // 繼續下一個，如果已經遍歷完，則失敗 if (index < 0) { return false; } // 添加當前元素或者放棄當前元素 return canPartition(nums, index - 1, canIncrease - nums[index], canDecrease) || canPartition(nums, index - 1, canIncrease, canDecrease - nums[index]); }}/<code>提交OK，從時間上來看，比之前的動態規劃更快。
總結
以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要涉及的是動態規劃，類似揹包問題，主要還是需要找出狀態轉移方程，優化時可以考慮採用深度優先搜索。
有興趣的話可以訪問我的博客或者關注我的公眾號、頭條號，說不定會有意外的驚喜。
https://death00.github.io/
分享到:
閱讀更多 健程之道 的文章
