BinarySearch 0605 Equal Partitions

Problem statement

https://binarysearch.com/problems/Equal-Partitions/

Solution

Equal to Leetcode 0416. Partition Equal Subset Sum.

Complexity

Time complexity is O(N*n), where N = sum(A) and n = len(A). Space complexity is O(N). Note, that in practice however it will work several times faster than usual dp due to fast bit operations.

Code

class Solution:
    def solve(self, A):
        a = reduce(lambda a, num: a|(a<<num), A, 1)
        return sum(A)%2 == 0 and a & (1 << (sum(A)//2)) != 0