416. Partition Equal Subset Sum

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # time O(N*_sum) space time O(N*_sum)
        # step1: check if posibble to equal
        _sum = sum(nums)
        size = len(nums)
        if _sum%2 != 0 :
            return False
        avg  = _sum//2
        # dp[i][j]: first i numbers can be summed up to  j 
        dp = [[False for _ in range(avg+1)] for x in range(size+1)]
        # step2: initialize base case 
        for i in range(size+1):
            dp[i][0] = True
        # step3: state transition
        for i in range(1,size+1):
            for j in range(1,avg+1):
                # step3.1:  when current weight has remaining, can choose to pick nums[i-1] or not to pick
                if j -nums[i-1] >= 0:    
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
                # step3.2 when current weight has not remaining, can only choose not to pick nums[i-1]
                else:
                    dp[i][j] = dp[i-1][j]
        # step4 return status when choose first size items and to turn into avg (sum)
        return dp[size][avg]

Optimization: Space Compression

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # time O(N*_sum) space time O(_sum)
        # step1: check if posibble to equal
        _sum = sum(nums)
        size = len(nums)
        if _sum%2 != 0 :
            return False
        avg  = _sum//2
        # dp[j]: can subset be summed up to j weight  
        dp = [False for _ in range(avg+1)]
        # step2: initialize base case 
        dp[0] = True 
        # step3: state transition
        for i in range(1,size+1):
            # !! note j can only in reverse order to avoid overwritten updated state 
            for j in range(avg,-1,-1):
                # step3.1:  when current weight has remaining, can choose to pick nums[i-1] or not to pick
                if j -nums[i-1] >= 0:    
                    dp[j] = dp[j] or dp[j-nums[i-1]]
                #print(i,j,dp)
        # step4 return if subset can be found to turn into avg (sum)
        #print(dp)
        return dp[avg]

to Better understand each steps state change: i j dp[0:avg+1] 1 11[True, False, False, False, False, False, False, False, False, False, False, False] 1 10[True, False, False, False, False, False, False, False, False, False, False, False] 1 9 [True, False, False, False, False, False, False, False, False, False, False, False] 1 8 [True, False, False, False, False, False, False, False, False, False, False, False] 1 7 [True, False, False, False, False, False, False, False, False, False, False, False] 1 6 [True, False, False, False, False, False, False, False, False, False, False, False] 1 5 [True, False, False, False, False, False, False, False, False, False, False, False] 1 4 [True, False, False, False, False, False, False, False, False, False, False, False] 1 3 [True, False, False, False, False, False, False, False, False, False, False, False] 1 2 [True, False, False, False, False, False, False, False, False, False, False, False] 1 1 [True, True, False, False, False, False, False, False, False, False, False, False] 1 0 [True, True, False, False, False, False, False, False, False, False, False, False] 2 11[True, True, False, False, False, False, False, False, False, False, False, False] 2 10[True, True, False, False, False, False, False, False, False, False, False, False] 2 9 [True, True, False, False, False, False, False, False, False, False, False, False] 2 8 [True, True, False, False, False, False, False, False, False, False, False, False] 2 7 [True, True, False, False, False, False, False, False, False, False, False, False] 2 6 [True, True, False, False, False, False, True, False, False, False, False, False] 2 5 [True, True, False, False, False, True, True, False, False, False, False, False] 2 4 [True, True, False, False, False, True, True, False, False, False, False, False] 2 3 [True, True, False, False, False, True, True, False, False, False, False, False] 2 2 [True, True, False, False, False, True, True, False, False, False, False, False] 2 1 [True, True, False, False, False, True, True, False, False, False, False, False] 2 0 [True, True, False, False, False, True, True, False, False, False, False, False] 3 11[True, True, False, False, False, True, True, False, False, False, False, True] 3 10[True, True, False, False, False, True, True, False, False, False, False, True] 3 9 [True, True, False, False, False, True, True, False, False, False, False, True] 3 8 [True, True, False, False, False, True, True, False, False, False, False, True] 3 7 [True, True, False, False, False, True, True, False, False, False, False, True] 3 6 [True, True, False, False, False, True, True, False, False, False, False, True] 3 5 [True, True, False, False, False, True, True, False, False, False, False, True] 3 4 [True, True, False, False, False, True, True, False, False, False, False, True] 3 3 [True, True, False, False, False, True, True, False, False, False, False, True] 3 2 [True, True, False, False, False, True, True, False, False, False, False, True] 3 1 [True, True, False, False, False, True, True, False, False, False, False, True] 3 0 [True, True, False, False, False, True, True, False, False, False, False, True] 4 11[True, True, False, False, False, True, True, False, False, False, False, True] 4 10[True, True, False, False, False, True, True, False, False, False, True, True] 4 9 [True, True, False, False, False, True, True, False, False, False, True, True] 4 8 [True, True, False, False, False, True, True, False, False, False, True, True] 4 7 [True, True, False, False, False, True, True, False, False, False, True, True] 4 6 [True, True, False, False, False, True, True, False, False, False, True, True] 4 5 [True, True, False, False, False, True, True, False, False, False, True, True] 4 4 [True, True, False, False, False, True, True, False, False, False, True, True] 4 3 [True, True, False, False, False, True, True, False, False, False, True, True] 4 2 [True, True, False, False, False, True, True, False, False, False, True, True] 4 1 [True, True, False, False, False, True, True, False, False, False, True, True] 4 0 [True, True, False, False, False, True, True, False, False, False, True, True]