BinarySearch 0663 Arrange Symbols to Create Sum

Problem statement

https://binarysearch.com/problems/Arrange-Symbols-to-Create-Sum/

Solution

Equal to Leetcode 0494 Target Sum.

Complexity

It is o(n * M) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums, S):
        a = sum(nums) - S
        if a < 0 or a%2==1: return 0 
        S = [((1<<(i*21))+1) for i in nums]
        return reduce(lambda p, i:(p*i)&(1<<((a//2+1)*21))-1, S, 1)>>(21*a//2)