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
and1000
- The target sum will have always a value between
-1000
and1000
- 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)
We'll now take you through what you need to know.
How do I use this guide?
Access all course materials today
The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.