【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();      }  };