We need to decide whether it is possible to split the array into two groups where both groups have the same total. If both subsets have equal sum, then each subset's sum must be exactly half of the total array sum. If the total sum is odd, there is no way to split it evenly, so we return false right away.

Once we know the target is totalSum / 2, the problem becomes: can we find a subset of nums that adds up to exactly target? This is the classic 0/1 Knapsack / Subset Sum problem. Each number is either included in the subset or it is not, and we want to know if any combination of included numbers sums to the target exactly.

Key Constraints:

Intuition

Try every possible subset. For each element, we have two choices: include it in the subset or exclude it. If any combination of included elements sums to the target (totalSum / 2), we have found a valid partition.

This is a depth-first search through the decision tree. At each level, we pick one element and branch into "take it" or "leave it." If a branch reduces the remaining sum to exactly zero, we return true. Otherwise, we backtrack and try the other option.

Algorithm

Example Walkthrough

Code

The brute force explores up to 2^n subsets, which is far too slow for n = 200. Many recursive calls solve the same subproblem repeatedly. The next approach caches each result so the same (index, remaining) pair is never solved twice.

Intuition

The brute force recomputes the same subproblems many times. The state of each recursive call is fully described by two values: the current index and the remaining sum we need to reach. Once we have computed whether it is possible to form remaining from elements at positions index through n-1, that answer never changes, so we can store it and reuse it.

We keep a 2D memo table keyed by (index, remaining). Before doing any work, we check whether this state has been computed. If so, return the cached answer. If not, compute it, store it, and return.

Algorithm

Example Walkthrough

Code

The memo table uses O(n * target) space, but each row only depends on the row below it, so we store n rows when one would do. The next approach builds the table bottom-up and reduces it to a single 1D array.

Intuition

Instead of working top-down with recursion, we build the solution bottom-up. We define dp[j] as a boolean: can we form sum j using some subset of the elements processed so far?

We start with dp[0] = true, since sum 0 is reachable by taking nothing. Then for each number in the array, we update the DP array: if sum j - num was already reachable, then including num makes sum j reachable too.

The update iterates from right to left, from target down to num. Left-to-right iteration would let a single element be counted more than once: setting dp[j] from dp[j - num] and then, later in the same pass, setting dp[j + num] from the freshly updated dp[j], which reuses num. Right-to-left iteration reads dp[j - num] before it can be overwritten in this pass, so it reflects the state before num was added, and each element contributes at most once.

Algorithm

Example Walkthrough

Code