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

Approaches

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

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