Good morning! 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

    '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 our guided, illustrated walk-through.

How do I use this guide?