Target Sum

Moderate

+5 more companies

Solve now

Problem statement

You are given an array ‘ARR’ of ‘N’ integers and a target number, ‘TARGET’. Your task is to build an expression out of an array by adding one of the symbols '+' and '-' before each integer in an array, and then by concatenating all the integers, you want to achieve a target. You have to return the number of ways the target can be achieved.

For Example :

You are given the array ‘ARR’ = [1, 1, 1, 1, 1], ‘TARGET’ = 3. The number of ways this target can be achieved is:
1. -1 + 1 + 1 + 1 + 1 = 3
2. +1 - 1 + 1 + 1 + 1 = 3
3. +1 + 1 - 1 + 1 + 1 = 3
4. +1 + 1 + 1 - 1 + 1 = 3
5. +1 + 1 + 1 + 1 - 1 = 3
These are the 5 ways to make. Hence the answer is 5.

Input Format :

The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘TARGET’ representing the size of the given array and the target.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the array.

Output Format :

For each test case, print a single integer representing the number of ways to form a target.

Print a separate line for each test case.

Constraints :

1 <= T <= 10
1 <= N <= 25
-1000 <= TARGET <= 1000
0 <= ARR[i] <= 1000

Time Limit: 1 sec

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

In this approach, we will have a choice, for every element whether to include it with the positive sign or whether to include it with a negative sign.

So let’s see the steps that what exactly the approach should be:

Step1: First, decide the base case.

If the array is of 0 length then your output will be 1 because you have one way to make a zero target.
Another situation can be that the size of the array is zero, but the target is non-zero. Now there is no way to achieve the target, so your output will be zero.

Step 2: Now, let’s make the recursion calls. Two recursion calls will be made since we have two choices on every element:

We will take the element at zero indexes with a positive sign. So the target we are left with is ‘M’ - arr[0].
We will take the element at zero indexes with a negative sign. So the target we are left with is target + arr[0].

We will make a recursive function getNumOfWays(arr, target, index), where ‘arr’ is the array, ‘target’ is the target number and index is the index of the array we are looking at.

Algorithm:

In the getNumOfWays(arr, target, index) function
- If ‘index’ is more or equal to the length of ‘arr’ then
  - If ‘target’ is 0 return 1 otherwise return 0
- Return the sum of getNumOfWays(arr, target - arr[index] index + 1), and getNumOfWays(arr, target + arr[index] index + 1)
In the given function, simple return getNumOfWays(arr, target, 0)

Solve now

02 Approach

In this approach, we will try to memoise the previous solution by storing the answer to all the possible combinations of ‘index’ and ‘target’. So that we don’t have to recalculate similar recursive calls

We will make a recursive function getNumOfWays(arr, target, index, cache), where ‘arr’ is the array, ‘target’ is the target number and index is the index of the array we are looking at and ‘cache’ is any data structure that can hold the solution to previous recursive calls

Algorithm:

In the getNumOfWays(arr, target, index, cache):
- If ‘index’ is more or equal to the length of ‘arr’ then
  - If ‘target’ is 0 return 1 otherwise return 0
- If cache[index][target] exists return cache[index][target]
- Store the sum of getNumOfWays(arr, target - arr[index] index + 1), and getNumOfWays(arr, target + arr[index] index + 1) in cache[index][target]
- Return ‘cache[index][target]’
In the given function
- Create an array of maps equal to the size of ‘arr’ called ‘cache’
- Return getNumOfWays(arr, target, 0, cache)

Solve now

03 Approach

In this approach, we will build the solution from the bottom up, which means we will build smaller targets with only up to a few indices of the array. Then use that to make the next solutions. We will create a 2D matrix ‘dp’ where row refers to the size of the array and column refers to the sums we can achieve up to that index.

In this array on each cell, we will be storing the number of ways possible to achieve that sum.

We will create the list of hashmaps instead of the 2D matrix. Where ‘dp[i]’ will contain a hashmap with keys as all the possible sums up to index ‘i - 1’ and values as the number of ways to achieve that sum.

Algorithm:

Create an array of hashmaps ‘dp’ equal to the length of ‘arr’ + 1.
Set dp[0][0] as ‘1’
Iterate i from 0 to length of ‘arr’ - 1.
- Iterate through ‘key’ and ‘val’ through all the key values pairs of ‘dp[i]’
  - Increase ‘dp[i][key + arr[i - 1]]’ by ‘val’
  - Increase ‘dp[i][key - arr[i - 1]]’ by ‘val’
Return dp[arr.length][target]

Solve now

04 Approach

In this approach, we will note that in the last approach we need the hashmaps for only 2 days at a time, which are the current and the last day. So we can do the problem with only two hashmaps and swap the current map with the next hashmap after each iteration.

Algorithm:

If the length of the ‘arr’ is 0, return 0.
Create two hashmaps ‘dp’ and ‘next’
Set ‘dp[-arr[0]]’ and ‘dp[arr[0]]’ as ‘1’
Iterate ‘i’ from 1 to size of ‘arr’ -1
- Set ‘next’ as empty hashmaps.
- Iterate through ‘key’ and ‘val’ through all the key values pairs of ‘dp[i - 1]’
  - Increase ‘next[key + ‘arr[i]]’ by ‘val’
  - Increase ‘next[key - arr[i]]’ by ‘val’
- Set ‘dp’ as ‘next’
Return ‘dp[target]’