【leetcode刷題】T171-分割等和子集

• 2019 年 10 月 7 日
• 筆記

木又連續日更第8天（8/100）

木又的第171篇leetcode解題報告

動態規劃類型第16篇解題報告

leetcode第416題：分割等和子集

https://leetcode-cn.com/problems/partition-equal-subset-sum/

【題目】

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

注意:

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

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

【思路】

這道題還是有難度的，得轉換個思維。

兩個子集和相等，那麼每個子集和為整個數組和的一半。

那麼問題就轉換為：從數組nums中選擇n個數，使得他們的和等於sum(nums) // 2。

我們使用dp[i]表示數組和是否能夠得到該值，那麼對於數組nums的元素n，只要dp[i]為True，則dp[i+n]為True。

(修改dp數組時，一定從後往前修改，否則會讀到「臟數據」)

【程式碼】

python版本

class Solution(object):      def canPartition(self, nums):          """          :type nums: List[int]          :rtype: bool          """          # 2 * 單個數組和，肯定是偶數          target = sum(nums)          if target % 2 == 1:              return False            # 選擇n個數，和為target          target = target / 2          dp = [False] * (target + 1)          dp[0] = True          for n in nums:              ls = []              for i in range(len(dp)-1, -1, -1):                  # i可以，那麼i+n可以                  if dp[i] and i + n <= target:                      dp[i+n] = True            return dp[-1]  

C++版本

class Solution {  public:      bool canPartition(vector<int>& nums) {          int sum0 = 0;          for(auto n: nums)              sum0 += n;          // 只有和是偶數，才可能分成兩個和相等的數組          if(sum0 % 2 == 1)              return false;            // 選擇n個數，和為target          int target =  sum0 / 2;          vector<int> dp(target+1, false);          dp[0] = true;          for(auto n: nums){              for(int i = target; i >= 0; i--){                  if(dp[i] && i + n <= target)                      dp[i+n] = true;              }          }          return dp.back();      }  };