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