Teaching Kids Programming – Find Partition Equal Subset Sum (Bottom Up Dynamic Programming Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a 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

Technically we can apply bruteforce algorithms to solve this if the input size is small. There are subsequences/subset and checking each to see if it sums up to half takes O(N) time and thus overall time complexity is

The optimal solution is to use Dynamic Programming algorithm. Yesterday we talked about Top Down Dynamic Programming Algorithm to solve the equation dp(i, j) which means the possibility to have a subset sum to j with elements up to [:i+1] or [i:].

for k in nums,
or:
for k in nums.

Find Partition Equal Subset Sum (Bottom Up Dynamic Programming Algorithm)

We can save the DP values in two dimension array then start filling the values bottom up. The outer loop is the index of the numbers, and the inner loop is the subset sum. If dp[i] requires dp[i+1], we need to iterate the index backwards/downwards.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def canPartition(self, nums: List[int]) -> bool:        
        total = sum(nums)
        if total & 1:
            return False
        half = total // 2
        dp = [[False] * (half + 1) for _ in range(n + 1)]        
        for i in range(n):
            dp[i][0] = True                
        for i in range(n - 2, -1, -1):
            for j in range(half, -1, -1):
                if j < nums[i]:
                    dp[i][j] = dp[i + 1][j]
                else:
                    dp[i][j] = dp[i + 1][j] or dp[i + 1][j - nums[i]]                    
        return dp[0][half]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:        
        total = sum(nums)
        if total & 1:
            return False
        half = total // 2
        dp = [[False] * (half + 1) for _ in range(n + 1)]        
        for i in range(n):
            dp[i][0] = True                
        for i in range(n - 2, -1, -1):
            for j in range(half, -1, -1):
                if j < nums[i]:
                    dp[i][j] = dp[i + 1][j]
                else:
                    dp[i][j] = dp[i + 1][j] or dp[i + 1][j - nums[i]]                    
        return dp[0][half]

If the dp[i] is based on dp[i-1], then we need to iterate the index forwards/upwards.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def canPartition(self, nums: List[int]) -> bool:        
        total = sum(nums)
        if total & 1:
            return False
        half = total // 2
    
        dp = [[False] * (half + 1) for _ in range(n + 1)]        
        for i in range(n):
            dp[i][0] = True     
        for i in range(1, n):
            for j in range(half, -1, -1):
                if j < nums[i]:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
        return dp[n - 1][half]       

class Solution:
    def canPartition(self, nums: List[int]) -> bool:        
        total = sum(nums)
        if total & 1:
            return False
        half = total // 2
    
        dp = [[False] * (half + 1) for _ in range(n + 1)]        
        for i in range(n):
            dp[i][0] = True     
        for i in range(1, n):
            for j in range(half, -1, -1):
                if j < nums[i]:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
        return dp[n - 1][half]       

Both time complexity is O(SN) where S is the subset sum (half) and N is the number of elements in the given array. The space complexity is O(SN).

Partition Equal Subset Sum via Optimised 1D Bottom Up Dynamic Programming Algorithm

dp[i] is purely based on dp[i-1] or dp[i+1], so we can compress the DP to one dimensional. To avoid conflicts of updating the dp value, we need to iterate the sum downwards.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def canPartition(self, nums: List[int]) -> bool:        
        total = sum(nums)
        if total & 1:
            return False
        half = total // 2                    
        n = len(nums)
       
        dp = [True] + [False] * half
        for j in nums:
            for i in range(half, 0, -1):
                if j <= i:
                    dp[i] = dp[i] | dp[i - j]
        return dp[half]   

class Solution:
    def canPartition(self, nums: List[int]) -> bool:        
        total = sum(nums)
        if total & 1:
            return False
        half = total // 2                    
        n = len(nums)
       
        dp = [True] + [False] * half
        for j in nums:
            for i in range(half, 0, -1):
                if j <= i:
                    dp[i] = dp[i] | dp[i - j]
        return dp[half]   

The time complexity is O(SN) and the space complexity is O(S).

Partition Equal Subset Sum Algorithms

• Teaching Kids Programming – Find Partition Equal Subset Sum (Top Down Dynamic Programming Algorithm)
• Partition Equal Subset Sum Algorithms using DFS, Top-Down and Bottom-up DP
• Teaching Kids Programming – Find Partition Equal Subset Sum (Bottom Up Dynamic Programming Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —