Good afternoon! Here's our prompt for today.

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

1[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:

1let arr = [2, 1, 3, -2]
2arr.reduce((a,b) => a + b, 0)
3// sum to 4
4
5arr = [-2, 1, 3, 2]
6arr.reduce((a,b) => a + b, 0)
7// 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:

1numSignWays([2, 1, 3, 2], 2)
2// 3
3// because 3 ways
4// -2, -1, +3, +2 sum to 2
5// +2, +1, -3, +2 sum to 2
6// +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)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

​

def num_sign_ways(nums, target):

    # fill in

    return nums

​

​

# Node definition

class Node:

    def __init__(self, val):

        self.val = val

        self.left = None

        self.right = None

​

​

# Regular binary trees

tree1 = Node(4)

tree1.left = Node(1)

tree1.right = Node(3)

​

tree2 = Node(5)

tree2.left = Node(10)

tree2.left.left = Node(17)

tree2.left.right = Node(3)

tree2.right = Node(8)

​

# Binary search trees

tree3 = Node(6)

tree3.left = Node(3)

​

tree4 = Node(5)

Here's our guided, illustrated walk-through.

How do I use this guide?