Program to find number of ways we can arrange symbols to get target in Python?

Suppose we have a list of non-negative numbers called nums and also have an integer target. We have to find the the number of ways to arrange + and - in nums such that the expression equals to target.

So, if the input is like nums = [2, 3, 3, 3, 2] target = 9, then the output will be 2, as we can have -2 + 3 + 3 + 3 + 2 and 2 + 3 + 3 + 3 – 2.

To solve this, we will follow these steps:

• s := sum of all numbers in nums

• if (s + target) mod 2 is not same as 0 or target > s, then

  • return 0

• W := quotient of (s + target) / 2

• dp1 := a list of size (W + 1) and fill with 0

• dp1[0] := 1

• dp2 := A list of size (W + 1) and fill with 0

• for i in range 0 to size of nums, do

  • for j in range 0 to W + 1, do

    • if j >= nums[i], then

      • dp2[j] := dp2[j] + dp1[j - nums[i]]

  • for j in range 0 to W + 1, do

    • dp1[j] := dp1[j] + dp2[j]

    • dp2[j] := 0

• return last element of dp1

Let us see the following implementation to get better understanding:

Example

 Live Demo

class Solution:    def solve(self, nums, target):       s = sum(nums)       if (s + target) % 2 != 0 or target > s:          return 0       W = (s + target) // 2       dp1 = [0] * (W + 1)       dp1[0] = 1       dp2 = [0] * (W + 1)       for i in range(len(nums)):          for j in range(W + 1):             if j >= nums[i]:                dp2[j] += dp1[j - nums[i]]             for j in range(W + 1):                dp1[j] += dp2[j]                dp2[j] = 0          return dp1[-1] ob = Solution() nums = [2, 3, 3, 3, 2] target = 9 print(ob.solve(nums, target))

Input

[2, 3, 3, 3, 2], 9

Output

2