https://leetcode.com/problems/partition-equal-subset-sum

We are asked if we can choose sum numbers such that the give in sum our number. We can do it in DP way with complexity $O(mn)$, where $n$ is amount of numbers and $m$ is sum of all numbers. This is classical discrete knapsack problem. Let dp[i][j] means whether the specific sum j can be gotten from the first i numbers. Then we can update it in $O(1)$: dp[i][j] = dp[i-1][j-A[i-1]] or dp[i-1][j]. Actually, we do not need $O(mn)$ memory, just $O(m)$: initialize it with False, except zero element, which is True. Then add first number and update some dp[A1] = True, then second number and so on.

The idea here is to use usual dp with states, but to encode them with numbers. Let me explain on small example, what I mean. Imagine, that we have numbers A = [1,5,11,5], then let us start with a = 1:

  1. Step 1, what numbers, we can get, using only first number 1: it is only 1, so a = 11: we have onese on the places we can represent.
  2. Step 2, what numbers we can get, using only numbers 1 and 5: it is 1, 5 and 6, and a = 1100011
  3. Step 3, what numbers we can get, using numbers 1, 5, 11? it is 1,5,6,11,12,16,17, so a = 110001100001100011, where we have ones on exactly the places which can be represented with some sum of numbers.
  4. Step 4, we have now a = 11000110001110001100011

Finally, we need to just check if we have 1 in the middle of this number or not.

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.

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

Update: oneliner from rkmd:

return not (t := sum(A)) % 2 and reduce(lambda a, x: a | a << x, A, 1) & 1 << t // 2

If you have any questions, feel free to ask. If you like solution and explanations, please Upvote!

If you like the solution, you can upvote it on leetcode discussion section: Problem 0416