partition-equal-subset-sum

Try it on leetcode

Description

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: 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

Solution(Python)

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) & 1:
            return False
        total = sum(nums) // 2
        n = len(nums)
        memo = {}

        def dfs(t, index):
            if t in memo:
                return memo[t]
            if t < 0:
                return 0
            elif t == 0:
                return 1
            for i in range(index, n):
                if dfs(t - nums[i], i + 1):
                    memo[t] = 1
                    return 1
            memo[t] = 0
            return 0

        ans = dfs(total, 0)
        return ans