416. Partition Equal Subset Sum

Given a non-empty array 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.

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

Solution in python:

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        length = len(nums)
        total = sum(nums)
        if total % 2 != 0:
            return False
        total //= 2
        flag = [[None for i in range(total+1)] for j in range(length+1)] 
        for i in range(length+1):
            flag[i][0] = True
        for j in range(total+1):
            flag[0][j] = False
        for i in range(1, length+1):
            for j in range(1, total+1):
                if j - nums[i-1] >= 0:
                    flag[i][j] = flag[i-1][j] or flag[i-1][j-nums[i-1]]
                else: continue
        return flag[length][total]

Complexity analysis:

• Time complexity: O(N*M)
• Space complexity: O(N*M)