Subset Sum Solver
AlgorithmsMediumVerify if a subset of elements can sum up exactly to a target sum.
Alt+Shift+S
Configuration Panel
Subset Sum Feasibility Grid (backtrack path highlighted)
DP table is empty.
Time Complexity
O(N * target)
Space Complexity
O(N * target) / O(target) optimized
Conceptual Overview
The Subset Sum problem decides if there exists a subset of non-negative integers from a set whose sum is exactly equal to a target sum S.
Recurrence Relation
dp[i][j] = dp[i-1][j] || dp[i-1][j - arr[i-1]] if arr[i-1] <= j else dp[i-1][j]
State Transitions
Performs boolean OR logic between skipping current element (dp[i-1][j]) and taking current element (dp[i-1][j - arr[i-1]]).
Source: CP-Algorithms dynamic programming reference