Mark As Completed Discussion

Good afternoon! Here's our prompt for today.

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

JAVASCRIPT
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.

Description

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:

JAVASCRIPT
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:

JAVASCRIPT
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?

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

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.

Returning members can login to stop seeing this.