Partition Equal Subset Sum (DP)

A Cup of Persian Buttercup © Diane Khambu

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.

Since we need to partition into subsets, we’ll check what the target sum for each subset will be. If each subset cannot have the same sum, then we return False else we’ll calculate if target can be reduced to 0 by either subtracting or not subtracting elements in nums array. Let’s see the recursive top-down approach:

from typing import List

def partition_helper(nums: List[int], target: int, idx: int, n: int) -> bool:
    if target == 0:
        return True
    elif idx == n or target < 0:
        return False
    return partition_helper(nums, target-nums[idx], idx+1, n) or \
           partition_helper(nums, target, idx+1, 0)

def can_partition(nums: List[int]) -> bool:
    total = sum(nums)
    if total % 2 == 1: # needs to be evenly divided
        return False
    target = total // 2
    n = len(nums)

    return partition_helper(nums, target, 0, n)

nums = [1, 5, 11, 5]
print(can_partition(nums)) # prints True
nums2 = [1, 2, 3, 5]
print(can_partition(nums2)) # prints False

The recursive tree for the implementation of nums array [1, 5, 11, 5] where target is 11 looks like this:

recursive tree

Once we reach the base cases including where target is 0 , the OR of False and True gives us the desired result. As we pop off the stack the OR of many False and one True is True.

To avoid repetitive calculation of already calculated idx and target we’ll use cache . Here’s the implementation:

from typing import List, Set, Tuple

def partition_helper(nums: List[int], target: int, idx: int, n: int, \
                     cache: Set[Tuple[int, int]]) -> bool:
    if target == 0:
        return True
    elif idx == n or target < 0:
        return False
    elif (idx, target) in cache:
        return False
    res = partition_helper(nums, target-nums[idx], idx+1, n, cache) or \
          partition_helper(nums, target, idx+1, n, cache)

    if res:
        return True
    cache.add((idx, target))
    return False

def can_partition(nums: List[int]) -> int:
    total = sum(nums)
    if total % 2 == 1: # needs to be evenly divided
        return False
    
    target = total // 2
    cache = set()
    n = len(nums)
    return partition_helper(nums, target, 0, n, cache)

nums = [1, 5, 11, 5]
print(can_partition(nums)) # prints True
nums2 = [1, 2, 3, 5]
print(can_partition(nums2)) # prints False

Now is the Dynamic Programming (DP) implementation. Two things to remember for DP are identifying subproblem and using the subproblems’ solution to build target’s answer.

If we had nums's length as 0 and target sum as 0 , then we know answer is True. If target is 0 then again the answer is True. If an element in nums array is less than the target, we can either subtract the element from the target or not. For element greater than target we’ll have answer from previous calculation. Let’s see this in implementation:

from typing import List

def can_partition(nums: List[int]) -> bool:
    total = sum(nums)
    if total % 2 == 1: # must be evenly divisible
        return False

    target = total // 2
    n = len(nums)

    dp = [[False for _ in range(target+1)] for _ in range(n+1)]
    dp[0][0] = True # nums array of length 0 and target of 0 is True

    for i in range(1, n+1): 
        for j in range(target+1):
            if j == 0: # target of 0
                dp[i][j] = True 
            elif nums[i-1] <= j: # include the nums[i-1] or not
                dp[i][j] = dp[i-1][j - nums[i-1]] or dp[i-1][j] 
            else:
                dp[i][j] = dp[i-1][j]

    return dp[n][target]

nums = [1, 5, 11, 5]
print(can_partition(nums)) # prints True
nums2 = [1, 2, 3, 5]
print(can_partition(nums2)) # prints False

Voila! We can now calculate if an array can be partitioned equally.

Let’s check another question — ‘Get Maximum in Generated Array’

You are given an integer n . A 0-indexed integer array nums of length n+1 is generated in the following way:

• nums[0] = 0
• nums[1] = 1
• nums[2*i] = nums[i] when 2 <= 2*i <= n
• nums[2*i+1] = nums[i] + nums[i+1] when 2 <= 2*i+1 <= n

Return the maximum integer in the array nums .

What we see from the rule is that for even index left hand side of the equation it is nums[i] and for odd index it is nums[i] + nums[i+1] . Another thing to keep in mind is that for the left had side of the equation, the rule shows for 2*i or 2*i+1 indexes. Hence to get for just i and i+1 index, we’ll divide both sides’s indexes by 2.

def get_maximum_generated(n: int) -> int:
    nums = [0] * (n+1)

    nums[0] = 0
    nums[1] = 1
    
    for i in range(2, n+1):
        if i%2 == 0:
            nums[i] = nums[i//2] # divide both sides by 2
        else:
            nums[i] = nums[i//2] + nums[i//2 + 1] # divide both sides by 2
    return max(nums)

n = 7
print(get_maximum_generated(n)) # prints 3

These are some tips of substituting * by // or // by * to put in your problem solving tools.

That’s all for this post. Congratulations for coming this far! 🎈

See you in my next post. Until then, ✨.

Inspiration:

• leetcode

You can support me in Patreon!