Close
Topic list
Target Sum
MEDIUM
Dynamic Programming
Arrays
Topics (Covered in this problem)
Problem solved
Skill meter
Dynamic Programming
-
Arrays
-
Other topics
Problem solved
Skill meter
Strings
-
Matrices (2D Arrays)
-
Sorting
-
Binary Search
-
-
Stacks & Queues
-
Trees
-
Graph
-
Greedy
-
Tries
-
Binary Search Trees
-
Heap
-
Bit Manipulation
-

# Target Sum

Contributed by
Paritosh Singh
Medium
Share

## 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, Constraints, Images )
##### 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
``````
Console