New update is available. Click here to update.

Last Updated: 10 Feb, 2022

Moderate

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

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

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

```
1 <= T <= 10
1 <= N <= 25
-1000 <= TARGET <= 1000
0 <= ARR[i] <= 1000
Time Limit: 1 sec
```

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

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**

- If ‘
- Return the sum of
**getNumOfWays(arr, target - arr[index] index + 1)**, and**getNumOfWays(arr, target + arr[index] index + 1)**

- If
- In the given function, simple return
**getNumOfWays(arr, target, 0)**

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

- 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 ‘
- 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]’**

- If
- In the given function
- Create an array of maps equal to the size of
**‘arr**’ called**‘cache’** - Return
**getNumOfWays(arr, target, 0, cache)**

- Create an array of maps equal to the size of

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**’

- Increase ‘

- Iterate through ‘
- Return
**dp[arr.length][target]**

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**’

- Increase ‘
- Set ‘
**dp**’ as ‘**next**’

- Set
- Return ‘
**dp[target]**’

Similar problems