Last Updated: 10 Feb, 2022
##### Target Sum
Moderate
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.
``````
Approaches

## 01Approach

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)