leetcode-dp

416. Partition Equal Subset Sum.py

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        """
        After thinking in a way, whether it's able to find a subset of element could construct half of sum of all elments in the array. Then, it's a typical 0/1 knapsacks problem.
        
        Let's assume dp[i][j] means whether the specific sum j can be gotten from the first i numbers or not
        
        T: O(n*w), where n is number of elements in array and w is half of sum
        S: O(n*w)
        """
        s = sum(nums)
        n, half_sum = len(nums), s // 2
        # edge case
        if s%2 or max(nums) > half_sum: 
            return False
       
        # step1: for reason we plus 1 in range is we dp[0][0] represents whether we could construct sum 0 with 0 first elements
        dp = [[False for col in range(half_sum+1)] for row in range(n+1)]
        for i in range(n+1):
            dp[i][0] = True
        # step2: recursive formulatin
        for i in range(1, n+1):
            for j in range(1, half_sum+1):
                if j - nums[i-1] >= 0:
                    # when j - nums[i-1] >= 0 larger than 0 means we have capacity to choose i th element in array. 
                    # However, we can either choose to use or not to use the i th element.
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
                else:
                    dp[i][j] = dp[i-1][j] 
        # step3:
        return dp[n][half_sum]
    
    def canPartition(self, nums: List[int]) -> bool:
        """
        Optimized version from space complexity.
        
        dp[x]: whether we can construct sum x with a subset of element.
        
        Note:
            1. The trick is to update the array from right to left for each new weight due to recursive formulation in 1-D.
            So, the reason why we need to process higher sum first is to prevent from overwritting previous solution computed already.
            2. No matter we pick i element or not, whether we can construct sum x with a first i element is all depend on 
            whether we can construct sum x with a first i-1 element. So, recursive formulation and dp table can be reduced to 1-D.
            
        T: O(n*w), where n is number of elements in array and w is half of sum
        S: O(w)
        """
        n = len(nums)
        s = sum(nums)
        
        if s % 2:
            return False

        half_sum = s // 2

        dp = [False for _ in range(half_sum + 1)]
        dp[0] = True

        # for i, num in enumerate(nums, 1):
        #     for x in range(half_sum, num - 1, -1):
        #         # faster but not that readable
        #         dp[x] = dp[x] or dp[x - num]
                
        for i in range(1, n+1):
            for j in range(half_sum, 0, -1):
                if j - nums[i-1] >= 0:
                    # the answer is based on we either take i element or not take i element.
                    dp[j] = dp[j] or dp[j - nums[i-1]]
                    
        return dp[half_sum]