Subset Sum Problem (DP)
H · hardP · Verified PYQarraysdp
Problem
Given an array and a target sum S, determine if there exists a subset with sum equal to S.
Example
Input
5 9 3 1 4 2 2
Output
YES
DP: dp[j] = True if sum j is achievable. For each element, update dp from right to left.