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
'PASSED: ' + 'numSignWays([10,9,4,7,5,5,4,2,2], 10) should return 15'
var assert = require('assert');
​
function numSignWays(nums, target) {
// Fill in this method
return nums;
}
​
function helper(step, sum, hash, nums, target) {
// Fill in this method
return step;
}
​
numSignWays([2, 1, 3, 2], 4);
​
function Node(val) {
this.val = val;
this.left = null;
this.right = null;
}
​
// Regular binary trees
var tree1 = new Node(4);
tree1.left = new Node(1);
tree1.right = new Node(3);
​
var tree2 = new Node(5);
tree2.left = new Node(10);
tree2.left.left = new Node(17);
tree2.left.right = new Node(3);
Here's how we would solve this problem...
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.