Here is the interview question prompt, presented for reference.

We're given an array of positive integers like the following:

[2, 1, 3, 2]

Imagine that we're allowed to make each element of the array either a positive or negative number, indicated by a signage -- either a plus (+) or minus (-) sign that appears before it. If we sum up all the signed elements, we will get a total sum of all the signed numbers.

The total sum can often be calculated via many permutations of the elements. For example, let's say we had a target sum of 4, that is, we wish to have our signed numbers sum up to 4. What we'd see is that there are two ways to arrive there:

let arr = [2, 1, 3, -2]
arr.reduce((a,b) => a + b, 0)
// sum to 4

arr = [-2, 1, 3, 2]
arr.reduce((a,b) => a + b, 0)
// sum to 4

So the answer's 2.

If we're given a target number, can you define a method numSignWays(nums: array, target: integer) that would return us the number of permutations possible to sum to it? For example, if the above array of numbers had a target sum of 2 instead, there are 3 ways:

numSignWays([2, 1, 3, 2], 2)
// 3
// because 3 ways
// -2, -1, +3, +2 sum to 2
// +2, +1, -3, +2 sum to 2
// +2, -1, +3, -2 sum to 2

You may assume all numbers in the array are >= 1.

Constraints

• Length of the array <= 1000
• The array will always contain integer values between -1000 and 1000
• The target sum will have always a value between -1000 and 1000
• Expected time complexity : O(n^2)
• Expected space complexity : O(n)

You can see the full challenge with visuals at this link.