Partition in two equal subset¶

The algorithm works as follow:¶
1) Check if the sum of elements is even, if not return False¶
2) Apply knapstack without repetition to find a sequence that sums to sums/2: if this sequence exists, the sequence of remaining elements does also sum to sums/2¶
3) Return True if this sequence exists, False otherwise¶
In [ ]:
def canPartition(nums: List[int]) -> bool:
    sums = sum(nums)
    if sums % 2 == 1:
        return(False)

    # knapstack without repetition: find a sequence that sums to (sums / 2)
    sums /= 2
    knap = [[True] + [False for _ in range(int(sums))] for _ in range(2)]
    for x in nums:
        for i in range(x, len(knap[0])):
            knap[1][i] = knap[0][i] or knap[0][i-x]
        knap[0] = knap[1][:]

    return(knap[0][-1])