Partition Problem
AlgorithmsMediumDetermine if a set can be split into two equal-sum disjoint subsets.
Alt+Shift+P
Configuration Panel
Partition Feasibility Grid (backtrack path highlighted)
DP table is empty.
Time Complexity
O(N * target)
Space Complexity
O(N * target) table size
Conceptual Overview
The Partition Problem checks if a given set of positive integers can be partitioned into two subsets such that the sum of elements in both subsets is equal.
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 checks evaluating subset possibilities with or without elements.
Source: CP-Algorithms dynamic programming reference