LeetCode 416: Partition Equal Subset Sum

link

Assigning the positive numbers in two equal-sum subsets is same as creating one set having sum equal to half of the total sum.

We can use Dynamic Programming. This is like coin-change except a number cannot be reused.

Sub-problem

Let solutions[ (i, s) ] represent the sub-problem of creating a subset with target sum s using numbers in nums[0…i]. Then,

solutions[ (i, s) ] = OR( {solutions[ (i-1, s) ], solutions[ (i-1, s-nums[i]) ]} )

When s < nums[i], only contributing sub-problem is solutions[ (i-1, s) ]

Order

The sub-problems form a grid and solutions[ (i, s) ] depends on sub-problems that are all in the earlier row and columns. So, processing rows (and columns) in sequence gives us a topological ordering of the sub-problems.

If there $n$ numbers and their sum is $S$ , then time: $\mathcal{O}(n \cdot S)$ , space: $\mathcal{O}(n \cdot S)$ .

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        target_sum, r = divmod(total, 2)
        if r != 0:
            return False
        
        n = len(nums)
        dp = [
            [False for _ in range(target_sum+1)] for _ in range(n)
        ]
        # Solve trivial sub-problems
        for s in range(target_sum+1):
            dp[0][s] = (nums[0] == s)
        for i in range(1, n):
            for s in range(1, target_sum+1):
                # Edges from sub-problems
                # func1: OR
                take = dp[i-1][s-nums[i]] if s >= nums[i] else False 
                leave = dp[i-1][s]
                dp[i][s] = take or leave
        
        # func2: select last
        return dp[n-1][target_sum]

Note that a sub-problem has edges only from the sub-problems on the same or earlier columns of the previous row. So, if we process the rows top-to-bottom as before but process the columns right-to-left, we can save dp[i][s] in dp[i-1][s] because later sub-problems (for example, dp[i][s-1]) will not need dp[i-1][s]. That way, a one-dimensional dp suffices, reducing space complexity.

Time: $\mathcal{O}(n \cdot S)$ , space: $\mathcal{O}(S)$ .

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        target_sum, r = divmod(total, 2)
        if r != 0:
            return False
        
        n = len(nums)
        dp = [False for _ in range(target_sum+1)]
        # Solve trivial sub-problems
        for s in range(target_sum+1):
            dp[s] = (nums[0] == s)
        for i in range(1, n):
            for s in range(target_sum, -1, -1):
                # Edges from sub-problems
                # func1: OR
                take = dp[s-nums[i]] if s >= nums[i] else False 
                leave = dp[s]
                dp[s] = take or leave
        
        # func2: select last
        return dp[target_sum]

unreasonably effective