10.21

Idea
The problem is equivalent to asking whether one can reach the value M/2 with some subset of the numbers. If the total sum M is odd, the answer is immediately “NO”. Otherwise we run a classic subset-sum DP.

State
dp[i][s] = TRUE if among the first i elements we can obtain a sum of s, FALSE otherwise.

Recurrence
For each element v = si:
• Exclude it → dp[i-1][s]
• Include it → dp[i-1][s-v] (when s ≥ v)
Hence
dp[i][s] = dp[i-1][s] OR (s ≥ v AND dp[i-1][s-v]).

Initialization
dp[0][0] = TRUE; every other entry in row 0 is FALSE.

Answer
Return dp[n][M/2].

Time / Space
There are n rows and at most M/2 columns ⇒ O(nM) time. With a rolling array (prev → curr) space drops to O(M).

Python (pseudo-clean)

def can_partition(nums):
  M = sum(nums)
  if M % 2: # odd total ⇒ impossible
    return False
  target = M // 2

  dp = [False]*(target+1)
  dp[0] = True

  for v in nums:
    for s in range(target, v-1, -1):
      dp[s] = dp[s] or dp[s-v]

  return dp[target]

The double loop runs at most n·M/2 = O(nM), meeting the required complexity. If can_partition returns TRUE, the original set can be divided into two parts of equal sum; otherwise it cannot.

Back to Chapter 10