動機

真的就是DPㄟ

Problem

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

 

Example 1:

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

Example 2:

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

 

Constraints:

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

Sol

看起來是要找兩個set，但是總和是一樣的，所以變成看能不能從中湊出總和就好

class Solution:
    @functools.cache
    def f(self,i,cnt):
        if cnt < 0 or i < 0:
            return False
        elif cnt == 0:
            return True
        else:
            return self.f(i-1,cnt) or self.f(i-1,cnt-self.nums[i])
    def canPartition(self, nums: List[int]) -> bool:
        cnt = sum(nums)
        self.nums = nums
        
        if cnt % 2 == 1:
            return False
        
        cnt = cnt // 2
        return self.f(len(nums)-1,cnt)