Subset Sum Equal to Target
DP on Subsequences DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Subset Sum Equal to Target (Subset Sum Problem) and Dynamic Programming Approaches, Dynamic Programming, Subsequences, Memoization, Tabulation, Space Optimization, Recursion, Time Complexity, Space Complexity, Arrays, dynamic programming, memoization, tabulation, space optimization, recursion, time complexity analysis, DP on Subsequences / Subsets.
Subset Sum Equal to Target Problem Statement You are given an array ARR containing N positive integers and a target sum K. Your task is to determine if there exists any subset of ARR whose elements sum up to K. Return true if such a subset exists, otherwise return false. Input Specification The first line contains an integer N, representing the number of elements in the array. The second line contains N space separated positive integers, representing the elements of the array ARR. The third line contains an integer K, representing the target sum. Output Specification Print true if a subset with the target sum K exists, otherwise print false. Constraints 1 <= N 1 <= ARR[i] (elements are positive integers) 0 <= K Sample Test Case Input: Output: Explanation: Subsets that sum to 4 are {4} and {1, 3}.