Target Sum

Moderate
0/80
profile
Contributed by
171 upvotes
Asked in companies
ZSOLX GroupAmazon

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample input 1 :
2
5 3
1 1 1 1 1
4 3
1 2 3 1
Sample Output 2 :
5
2
Explanation For Sample Input 1 :
For the first test case, ‘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 get the target. Hence the answer is 5.

For the second test case, ‘ARR’ = [1, 2, 3, 1]. ‘TARGET’ = 3, The number of ways this target can be achieved is:
1. +1 - 2 + 1 + 3 = 3
2. -1 + 2 - 1 + 3 = 3
These are the 3 ways to get the target. Hence the answer is 2.
Sample Input 2 :
2
3 2
1 2 3
2 0
1 1
Sample Output 2 :
1
2
Hint

Try the brute force appoach

Approaches (4)
Brute Force

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)
Time Complexity

O( 2 ^ N ), where N is the number of elements in the array.

 

For each index, we are making 2 recursive calls, which will lead to the total number of ~2^N recursive calls

Hence the overall time complexity is O( 2 ^ N ).

Space Complexity

O( N ), where N is the number of elements in the array.

 

The recursion stack can only go as deep as the number of elements in the array that is ~N

Hence the overall space complexity is O ( N ).

Code Solution
(100% EXP penalty)
Target Sum
Full screen
Console