Problem statement

https://leetcode.com/problems/target-sum/

Solution

One way to solve this problem is just to check all 2^n possible combinations, using dfs with backtracking. Complexity will be O(2^n).

We can also solve this problem, using dp. We can reformulate: we need to find some subset of nums, such that its sum is equal to (S - M)/2, where M is sum of all numbers. Denote by dp[i] numbers of ways to construct number i. Then we can solve this problem in O(n * M) time complexity and O(M) space complexity.

There is also very smart my solution, I am proud of, using generative functions, which is currently the fastest solution on leetcode for this problem. The idea is to take base x = 2**21 and then multiply polynoms $(1 + x^{s_1})\cdot \dots \cdot (1 + x^{s_n})$. We can take this x, because n <= 20 and coefficients will be no more than 2^20.

Complexity

We can say it is O(n * M) but with pretty small constant.

Code

class Solution:
    def findTargetSumWays(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)

Remark

See similar Problem 0322 Coin Change and 0518 Coin Change 2.