Partition Equal Subset Sum

Problem

Given an integer array nums, return true if the array can be split into two subsets with equal sum.

Intuition

"Split into two equal-sum subsets" has a quick reframe: the total must be even (call it 2T), and we need a subset summing to T. The other subset automatically sums to T by subtraction.

Now we have the subset sum problem: can we pick a subset of nums summing to T? That's a classic 0/1 knapsack — each item is either in or out, and we're asking a yes/no reachability question.

dp[i][j] = "using the first i items, can we sum to j?" Each item either joins the subset (dp[i - 1][j - nums[i - 1]]) or skips (dp[i - 1][j]). Take the OR.

dp[i][j] = dp[i - 1][j] || (j >= nums[i-1] && dp[i - 1][j - nums[i-1]])

The 1D collapse is the one space optimization everyone gets wrong once. Iterating j left-to-right would let the same item get counted twice (a fresh update at dp[j - x] would feed back into dp[j] in the same pass). Iterate j descending from T down to x so each item's effect propagates only forward in time. This is the hallmark move of 0/1 knapsack, and not just a trick — it's why it's called 0/1.

Approach

impl Solution {
    pub fn can_partition(nums: Vec<i32>) -> bool {
        let sum: i32 = nums.iter().sum();
        if sum % 2 != 0 {
            return false;
        }
        let target = (sum / 2) as usize;
        let n = nums.len();
        let mut dp = vec![vec![false; target + 1]; n + 1];
        dp[0][0] = true;
        for i in 1..=n {
            let x = nums[i - 1] as usize;
            for j in 0..=target {
                dp[i][j] = dp[i - 1][j] || (j >= x && dp[i - 1][j - x]);
            }
        }
        dp[n][target]
    }
}

function canPartition(nums: number[]): boolean {
  const sum = nums.reduce((a, b) => a + b, 0);
  if (sum % 2 !== 0) return false;
  const target = sum / 2;
  const n = nums.length;
  const dp: boolean[][] = Array.from({ length: n + 1 }, () => new Array(target + 1).fill(false));
  dp[0][0] = true;
  for (let i = 1; i <= n; i++) {
    const x = nums[i - 1];
    for (let j = 0; j <= target; j++) {
      dp[i][j] = dp[i - 1][j] || (j >= x && dp[i - 1][j - x]);
    }
  }
  return dp[n][target];
}

impl Solution {
    pub fn can_partition(nums: Vec<i32>) -> bool {
        let sum: i32 = nums.iter().sum();
        if sum % 2 != 0 {
            return false;
        }
        let target = (sum / 2) as usize;
        let mut dp = vec![false; target + 1];
        dp[0] = true;
        for &x in &nums {
            let x = x as usize;
            if x > target {
                continue;
            }
            // Descending — each item applied at most once per row.
            for j in (x..=target).rev() {
                if dp[j - x] {
                    dp[j] = true;
                }
            }
            if dp[target] {
                return true;
            }
        }
        dp[target]
    }
}

function canPartition(nums: number[]): boolean {
  const sum = nums.reduce((a, b) => a + b, 0);
  if (sum % 2 !== 0) return false;
  const target = sum / 2;
  const dp = new Array<boolean>(target + 1).fill(false);
  dp[0] = true;
  for (const x of nums) {
    if (x > target) continue;
    for (let j = target; j >= x; j--) {
      if (dp[j - x]) dp[j] = true;
    }
    if (dp[target]) return true;
  }
  return dp[target];
}

Trace

1D rolling on nums = [1, 5, 11, 5], target 11:

dp[11] = true. ✓ (Found after inserting the 11; we can stop there.)

Edge cases

• Odd total — early return false. A sum split into two equal halves must be even.
• Single element — always false (can't split one element into two non-empty halves).
• All zeros — true. Two empty subsets both sum to zero.
• Any x > target — skip it. Including a too-large value can never help reach target, and the unconditional dp[j - x] lookup would underflow.

Takeaway

Partition Equal Subset Sum is the 0/1 knapsack in disguise. Recognize the pattern: "pick a subset that satisfies a constraint" → subset-sum reachability DP.

The two DP skills this problem teaches are worth way more than the problem itself:

1. Reframe composite questions. "Split into two equal halves" became "hit target sum / 2" in one step of arithmetic.
2. Loop direction encodes item multiplicity. Descending j = 0/1 (each item once). Ascending j = unbounded (each item any number of times).

You'll use both in #494 Target Sum (another subset-sum reframe), #322 Coin Change, and #518 Coin Change II (ordering matters).