416. Partition Equal Subset Sum

Problem Statement

link: LeetCode.cn LeetCode 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:

Input: nums = [1,5,11,5] Output: true

Input: nums = [1,2,3,5] Output: false

Solution Approach

The solution approach utilizes dynamic programming to determine if it’s possible to partition the given array into two subsets with equal sums, leveraging a bottom-up approach to fill a boolean array representing reachable sums.

Algorithm

1. Initialize a boolean array dp of length target + 1, where target is half the sum of all elements in the input array, with dp[0] set to True since it represents the possibility of achieving a sum of 0.
2. Iterate through each element in the input array, and for each element nums[i], traverse the dp array from target down to nums[i], updating dp[j] to True if either dp[j] or dp[j - nums[i]] is True, indicating that a subset sum of j can be achieved by either including or excluding the current element.
3. Finally, return dp[target], which indicates whether it’s possible to partition the array into two subsets with equal sums.

Implement

    class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        #1 5 5 11      sum(nums)//2   11
        #dp[i][j] = dp[i-1][j] or dp[i][j - nums[i]] j >= nums[i]
        #dp[j] = dp[j - 1] or dp[j - nums[i]]
        if len(nums) < 2:
            return False
        total = sum(nums)
        if total % 2 != 0:
            return False
        target = total // 2
        dp = [True] + [False] * target
        for i, n in enumerate(nums):
            for j in range(target, n - 1, -1):
                dp[j] = dp[j] or dp[j - nums[i]]
        return dp[target]

    
    

Twitter  facebook  Email