Teaching Kids Programming – Find Partition Equal Subset Sum (Top Down 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

We can bruteforce/enumerate each possible subsets – this is as there will be subsequences (considering each element we can pick or skip). And to get the sum of a subset/subsequence, it takes O(N) time and thus the overall time complexity is

If the sum of entire array is odd, it is impossible to split into two equal parts (as each number is positive).

Check if Array can be Split to Two Equal Subset Sum via Top Down Dynamic Programming Algorithm

For each number, we can pick or skip – and if we pick, we need to update the remaining sum. If at any point, the sum becomes zero, we find a solution. If the sum becomes negative, we can backtrack.

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
        @cache
        def dfs(i, s):
            if i == len(nums):
                return s == 0
            if s == 0:
                return True
            if s < 0:
                return False
            return dfs(i + 1, s) or dfs(i + 1, s - nums[i])
        return dfs(0, half)

class Solution:
    def canPartition(self, nums: List[int]) -> bool:        
        total = sum(nums)
        if total & 1:
            return False
        half = total // 2
        @cache
        def dfs(i, s):
            if i == len(nums):
                return s == 0
            if s == 0:
                return True
            if s < 0:
                return False
            return dfs(i + 1, s) or dfs(i + 1, s - nums[i])
        return dfs(0, half)

We use @cache to implement the Top Down Dynamic Programming Algorithm aka Recursion with Memoization. The time complexity is O(SN) where S is the sum of the array and N is the number of positive numbers.

The dfs(i, s) means if we can have a subset from [i:] with sum s. We can also let it represent the subset [:i+1], thus:

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

class Solution:
    def canPartition(self, nums: List[int]) -> bool:        
        total = sum(nums)
        if total & 1:
            return False
        half = total // 2                    
        n = len(nums)
 
        @cache
        def dfs(i, s):
            if i < 0:
                return s == 0
            if s == 0:
                return True
            if s < 0:
                return False
            return dfs(i - 1, s) or dfs(i - 1, s - nums[i])
        return dfs(n - 1, half)     

class Solution:
    def canPartition(self, nums: List[int]) -> bool:        
        total = sum(nums)
        if total & 1:
            return False
        half = total // 2                    
        n = len(nums)

        @cache
        def dfs(i, s):
            if i < 0:
                return s == 0
            if s == 0:
                return True
            if s < 0:
                return False
            return dfs(i - 1, s) or dfs(i - 1, s - nums[i])
        return dfs(n - 1, half)     

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) —