Target Sum
DP on Subsequences DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Target Sum Problem: Counting Expressions with '+' and '-' to Reach a Target, Dynamic Programming, Recursion, Memoization, Tabulation, Space Optimization, Subset Sum, Arrays, Time Complexity, Space Complexity, Mathematical Algorithms, Edge Cases, Conditional Statements, Loops, edge cases, dynamic programming, memoization, tabulation, space optimization, recursion.
Problem Statement Given an array ARR of N integers and an integer Target, your task is to find the number of ways to assign + or signs to each integer in ARR such that the sum of these signed integers equals Target. For example, if ARR = [1, 2, 3, 1] and Target = 3: +1 2 + 3 + 1 = 3 (One way) 1 + 2 + 3 1 = 3 (Another way) Therefore, there are 2 ways. Input Specification The first line contains an integer N, the size of the array. The second line contains N space separated integers representing the elements of ARR. The third line contains an integer Target. Output Specification Print a single integer, the number of ways to achieve the Target sum. Constraints 1 <= N <= 50 0 <= ARR[i] <= 1000 1000 <= Target <= 1000 Sample Test Cases Sample Input 1: Sample Output 1: