Question

剑指 Offer II 101. 分割等和子串

题目描述

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

 

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：nums 可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：nums 不可以分为和相等的两部分

 

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

 

注意：本题与主站 416 题相同： https://leetcode.cn/problems/partition-equal-subset-sum/

解法

方法一

class Solution:
  def canPartition(self, nums: List[int]) -> bool:
    s = sum(nums)
    if s % 2 != 0:
      return False

    m, n = len(nums), (s >> 1) + 1
    dp = [[False] * n for _ in range(m)]
    for i in range(m):
      dp[i][0] = True
    if nums[0] < n:
      dp[0][nums[0]] = True

    for i in range(1, m):
      for j in range(n):
        dp[i][j] = dp[i - 1][j]
        if not dp[i][j] and nums[i] <= j:
          dp[i][j] = dp[i - 1][j - nums[i]]
    return dp[-1][-1]

class Solution {
  public boolean canPartition(int[] nums) {
    int s = 0;
    for (int x : nums) {
      s += x;
    }
    if (s % 2 != 0) {
      return false;
    }
    int m = nums.length, n = (s >> 1) + 1;
    boolean[] dp = new boolean[n];
    dp[0] = true;
    if (nums[0] < n) {
      dp[nums[0]] = true;
    }
    for (int i = 1; i < m; ++i) {
      for (int j = n - 1; j >= nums[i]; --j) {
        dp[j] = dp[j] || dp[j - nums[i]];
      }
    }
    return dp[n - 1];
  }
}

class Solution {
public:
  bool canPartition(vector<int>& nums) {
    int s = 0;
    for (int x : nums) s += x;
    if (s % 2 != 0) return false;
    int m = nums.size(), n = (s >> 1) + 1;
    vector<bool> dp(n);
    dp[0] = true;
    if (nums[0] < n) dp[nums[0]] = true;
    for (int i = 1; i < m; ++i) {
      for (int j = n - 1; j >= nums[i]; --j) {
        dp[j] = dp[j] || dp[j - nums[i]];
      }
    }
    return dp[n - 1];
  }
};

func canPartition(nums []int) bool {
  s := 0
  for _, x := range nums {
    s += x
  }
  if s%2 != 0 {
    return false
  }
  m, n := len(nums), (s>>1)+1
  dp := make([]bool, n)
  dp[0] = true
  if nums[0] < n {
    dp[nums[0]] = true
  }
  for i := 1; i < m; i++ {
    for j := n - 1; j >= nums[i]; j-- {
      dp[j] = dp[j] || dp[j-nums[i]]
    }
  }
  return dp[n-1]
}

方法二

class Solution:
  def canPartition(self, nums: List[int]) -> bool:
    s = sum(nums)
    if s % 2 != 0:
      return False

    m, n = len(nums), (s >> 1) + 1
    dp = [False] * n
    dp[0] = True
    if nums[0] < n:
      dp[nums[0]] = True

    for i in range(1, m):
      for j in range(n - 1, nums[i] - 1, -1):
        dp[j] = dp[j] or dp[j - nums[i]]
    return dp[-1]

方法三

class Solution:
  def canPartition(self, nums: List[int]) -> bool:
    s = sum(nums)
    if s % 2 != 0:
      return False
    target = s >> 1

    @cache
    def dfs(i, s):
      nonlocal target
      if s > target or i >= len(nums):
        return False
      if s == target:
        return True
      return dfs(i + 1, s) or dfs(i + 1, s + nums[i])

    return dfs(0, 0)