Partition Equal Subset Sum — Day 45(Python)

Photo by Will Francis on Unsplash

Today is another day with Dynamic Programming. Let’s jump right into the question.

416.Partition Equal Subset Sum

Given 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

The problem states that we need to divide the array into two sub-arrays such that the sum in both the sub-arrays is equal. In short, we need to find a subarray from the given array such that the sum of the subarray is equal to half of the sum of the array.

One of the early signs that we might not find a positive answer is when the sum of the array is an odd number. In that case, we can return False.

We have a list of numbers, and we are required to make some decisions. We need to decide if we want to include or exclude a number in the subarray to add up to the half sum. If we decide to include the number, we should be decreasing the same value from the half sum. Well, this reminds me of the Knapsack problem, which means we should start by solving the recursive solution to this problem.

Let us start solving the recursive solution.

Since we are solving using the recursive solution, we need to know the base condition. Our recursive condition should stop when we have reached the required sum, or we have visited all the numbers in our array. If we have reached the required sum, then we should return True, but if we cover all the numbers before reaching the required sum, we should return False

if required_sum == 0:
   return True
if l < 0:
   return False

Once we have identified the base condition, the next step is identifying the choices.

If the number at the current position is less than or equal to the required sum, we can either include it in the sub-array, or we can avoid it. Here “l” points to the index of the number for which we need to make the required choice.

if nums[l] <= required_sum:
   return checkPartition(nums, required_sum-nums[l], l-1) or checkPartition(nums, required_sum, l-1)

If the number at the current position is greater than the required sum, we will ignore the number.

if nums[l] > required_sum:
   return checkPartition(nums, required_sum, l-1)

The above code using the choice diagram that I made.

Choice Diagram

Let us look into the complete code.

class PartitionFinder:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if sum(nums)%2 != 0:
            return False
        half_sum = sum(nums)//2
        def checkPartition(nums, required_sum, l):
            if required_sum == 0:
                return True
            if l < 0:
                return False
            if nums[l] <= required_sum:
                return checkPartition(nums, required_sum-nums[l], l-1) or checkPartition(nums, required_sum, l-1)
            else:
                return checkPartition(nums, required_sum, l-1)
        
        return (checkPartition(nums, half_sum, len(nums)-1))

Complexity analysis.

Time Complexity

We have N numbers, and each time we have two choices, whether to include the item or to avoid it. Hence the time complexity is O(2^N).

Space Complexity.

We are making use of recursive calls that internally hold the stack, so the space complexity is O(2^N).

Now that we have found the recursive solution, let us see if we can memoize the solution.

To memoize, we need to identify what parameters change during each function call. In the above code, the required sum and the index of the element for which we need to make choice changes. We need a 2D array that will keep track of the required sum, the index and its boolean result. We will create the array with the size required sum + 1 and the length of the array + 1. We will be initializing the array with False. Since the current table holds only boolean values, how do we keep track of combinations of the required sum and index that we have already calculated? We can have another boolean array that is of the same size as the memoization table, initialized as False. When we calculate the result to intermediate combinations, we will mark it as True in the second table.

We have required data structures to memoize the intermediate results, now let us make the required changes in the recursive code.

One of the additions that we need to make is to check if the current combination of the required sum and index is visited. If yes, we will return the result directly. Else, we will save the calculated values in the memo table and then return the result.

Similar to the recursive solution, we still have two choices to make. We can either include the number or ignore it. The code is similar to recursive solution except for few changes

Let see look into the code and the changes.

class PartitionFinder:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if sum(nums)%2 != 0:
            return False
        half_sum = sum(nums)//2
        memo = [[False for j in range(half_sum+1)] for i in range(len(nums)+1)]
        visited = [[False for j in range(half_sum+1)] for i in range(len(nums)+1)]
        
        def checkPartition(nums, required_sum, l):
            if required_sum == 0:
                return True
            if l < 0:
                return False
            if visited[l][required_sum]:
                return memo[l][required_sum]
            if nums[l] <= required_sum:
                memo[l][required_sum] =  checkPartition(nums, required_sum-nums[l], l-1) or checkPartition(nums, required_sum, l-1)
                visited[l][required_sum] = True
                return memo[l][required_sum]
            else:
                memo[l][required_sum] = checkPartition(nums, required_sum, l-1)
                visited[l][required_sum] = True
                return memo[l][required_sum]
        
        return (checkPartition(nums, half_sum, len(nums)-1))

Complexity analysis.

Time Complexity

Since we are avoiding duplicate calculation by storing intermediate results in a 2-D array. The time complexity, in this case, is O(N*Required_sum), where N is the number of items.

Space Complexity.

We are creating a 2-D array of size )N*Required_sum), so the space complexity is O(N*Required_sum).

Let us try converting the memoized code to tabulated code. We can convert memoized code to tabulated code is by changing recursive step to iterative steps.

We will be keeping the 2D array(memo table) in which we stored the intermediate results. Our task will be filling the results in this memo table.

Similar to memoized code, we will be initialising the memo table with False value. We need to keep in mind, the rows represent each value in our nums array and the columns represent values until the required sum.

Next we need to fill the base case in our memo table. Let us recall the base conditions.

if required_sum == 0:
   return True
if l < 0:
   return False

If required sum is 0, it means we have found our answer. Hence we need to fill the entire first column as True. If we have traversed through all the numbers in the array and if required sum is greater than 0, then we haven't found our answer. Hence we need to fill the entire first row as False.

Next change we need to make in our memoized code is to replace “l” with “i”(row number) and “required_sum” with “j”(column number). The recursive call is replaced with the memo tables result. Thats is it! Simple isn't it!!

Let us look into the tabulated code.

class PartitionFinder:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if sum(nums)%2 != 0:
            return False
        half_sum = sum(nums)//2
        memo = [[False for j in range(half_sum+1)] for i in range(len(nums)+1)]
        
        for row in range(len(memo)):
            memo[row][0] = True
            
        for col in range(1,len(memo[0])):
            memo[0][col] = False
        
        for i in range(1,len(memo)):
            for j in range(len(memo[0])):
                if nums[i-1] <= j:
                    memo[i][j] =  memo[i-1][j-nums[i-1]] or memo[i-1][j]
                else:
                     memo[i][j] = memo[i-1][j]
        
        return memo[-1][-1]

Complexity analysis.

Time Complexity

We are creating a 2D array of size ((N+1)*(required sum + 1)) and traversing through the entire table once. Hence the time complexity is ((N+1)*(required sum + 1)).

Space Complexity.

We are creating a 2D array of size ((N+1)*(required sum + 1)) and hence, the space complexity is ((N+1)*(required sum + 1)).

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.