力扣416——分割等和子集

2020 年 2 月 19 日
筆記

這道題主要涉及的是動態規劃，類似背包問題，主要還是需要找出狀態轉移方程，優化時可以考慮採用深度優先搜索。

原題

給定一個只包含正整數的非空數組。是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。

注意:

每個數組中的元素不會超過 100
數組的大小不會超過 200

示例 1:

輸入: [1, 5, 11, 5]    輸出: true    解釋: 數組可以分割成 [1, 5, 5] 和 [11].

示例 2:

輸入: [1, 2, 3, 5]    輸出: false    解釋: 數組不能分割成兩個元素和相等的子集.

原題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 背包問題」，就是考慮數字是否選擇。

不選擇 nums[i]，如果在 [0, i – 1] 這個子區間內已經有一部分元素，使得它們的和為 j ，那麼 dp[i][j] = true；
選擇 nums[i]，如果在 [0, i – 1] 這個子區間內就得找到一部分元素，使得它們的和為 j – nums[i]，那麼 dp[i][j] = true；
其餘情況，dp[i][j] = false；

所以狀態轉移方程是：dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]

接下來我們看看程式碼：

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;          // 創建二維狀態數組，行：物品索引，列：容量（包括 0）          boolean[][] dp = new boolean[len][target + 1];            // 先填表格第 0 行，第 1 個數只能讓容積為它自己的背包恰好裝滿          if (nums[0] <= target) {              dp[0][nums[0]] = true;          }            // 再填表格後面幾行          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。

動態規劃——優化

時間上的優化，其實可以提前結束，只要滿足 target，就滿足了總和一半的條件，可以直接結束，並不需要全部算完。

空間上的優化，其實只需要一維即可，因為只用了上一次的所有情況，並不需要所有。

接下來我們看看程式碼：

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];      }  }

提交OK。

深度優先搜索

和動態規劃類似，只是換成了遞歸的寫法。

針對一個數字選還是不選的問題，要求選擇的數字之和達到一半，等價於不選擇的數字之和也達到了一半。

只是針對剪枝，需要提供更多一些的情況：可以先從小到大排序，然後從大的一方開始找，這樣可以快速失敗，因為當超過一半之後，可以直接結束。

接下來看看程式碼：

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]);      }  }

提交OK，從時間上來看，比之前的動態規劃更快。

總結

以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要涉及的是動態規劃，類似背包問題，主要還是需要找出狀態轉移方程，優化時可以考慮採用深度優先搜索。