LeetCode

Appearance

416. Partition Equal Subset Sum ​

题目 ​

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

 

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

 

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100
Related Topics
  • 数组
  • 动态规划

  • 👍 2377
  • 👎 0

    • 解法 ​

    py
    from typing import List
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        target = total // 2

        dp = [False] * (target + 1)
        dp[0] = True

        for num in nums:
            for i in range(target, num - 1, -1):
                dp[i] = dp[i] or dp[i - num]

        return dp[target]



        
# leetcode submit region end(Prohibit modification and deletion)

Solution().canPartition([1,5,11,5])

    复杂度分析 ​

    • 时间复杂度 O(n×target)
    • 空间复杂度 O(target)