Frontend Prep

Appearance

Partition Equal Subset Sum ​

Problem Statement ​

Given a non-empty array nums of positive integers, determine if the array can be partitioned into two subsets such that the sums of the two subsets are equal.

Example 1:

Input: nums = [1, 5, 11, 5]
Output: true
Explanation: [1, 5, 5] and [11] both sum to 11.

Example 2:

Input: nums = [1, 2, 3, 5]
Output: false

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

Difficulty: Medium

Pattern Recognition ​

  • What is the structure of the input? An array of positive integers.
  • What are we checking? Existence of a subset summing to half the total.
  • What pattern does this suggest? 0/1 knapsack DP — each number is included or excluded exactly once.
  • Why does this pattern fit? If the total is odd, the answer is trivially false. Otherwise, finding a subset summing to total/2 is the classical "subset sum" decision problem, solved by 1D knapsack DP.

Approach ​

Brute Force — Enumerate Subsets ​

Try every subset, check if its sum equals total/2.

Time: O(2^N). Space: O(N) recursion. Why insufficient: N up to 200 makes this 2^200 — hopeless.

Better — Memoized Recursion ​

canPartition(i, target) = can we reach target using elements from index i onward. Memoize on (i, target).

Time: O(N * sum). Space: O(N * sum).

Optimal — 1D Bottom-Up Knapsack ​

Key Insight: You only need a 1D boolean array dp[s] that records "is there a subset summing to exactly s?" Process each number once; iterate s from target down to num to avoid reusing the same number twice in one pass.

Step-by-step:

  1. Compute total = sum(nums). If odd, return false.
  2. target = total / 2.
  3. dp = boolean array of size target + 1, all false, dp[0] = true.
  4. For each num: for s = target down to num, dp[s] = dp[s] || dp[s - num].
  5. Return dp[target].

Time: O(N * target) = O(N * total / 2). Space: O(target).

Walkthrough ​

nums = [1, 5, 11, 5], total = 22, target = 11.

Initial dp: [T, F, F, F, F, F, F, F, F, F, F, F].

Process num=1: iterate s=11..1. Each dp[s] |= dp[s-1]. After: dp[0..1]=T.

s11109876543210
after 1FFFFFFFFFFTT

Process num=5: iterate s=11..5. dp[s] |= dp[s-5].

| after 5 | F | F | F | F | F | T | T | F | F | F | T | T |

(dp[5]=T from dp[0], dp[6]=T from dp[1].)

Process num=11: iterate s=11..11. dp[11] |= dp[0] = true.

| after 11 | T | F | F | F | F | T | T | F | F | F | T | T |

dp[11] == true — we can stop, but the algorithm finishes the last number anyway.

Answer: true.

Implementation ​

typescript
function canPartition(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const num of nums) {
    for (let s = target; s >= num; s--) {
      dp[s] = dp[s] || dp[s - num];
    }
  }
  return dp[target];
}
cpp
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        if (total % 2) return false;
        int target = total / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for (int num : nums)
            for (int s = target; s >= num; --s)
                dp[s] = dp[s] || dp[s - num];
        return dp[target];
    }
};

Watch out: Iterating s ascending instead of descending. Going up reuses the same number multiple times (that's the unbounded-knapsack variant, not what you want here).

Watch out: Forgetting the odd-total shortcut. Without it you waste a full DP pass on an impossible instance.

Watch out: Booleans in vector<bool> are bit-packed in C++. Fine for correctness, just be aware of the quirky reference semantics.

Complexity Analysis ​

TimeSpace
Brute Force (enumerate)O(2^N)O(N)
Memoized RecursionO(N * sum)O(N * sum)
1D Bottom-Up DPO(N * sum)O(sum)

Bottleneck: You must touch every (num, sum) pair once. With N up to 200 and numbers up to 100, sum up to 20000, which is 4 * 10^6 ops — fast.

Edge Cases ​

  1. Odd total — Immediate false.
  2. Single element — False (can't split one number into two equal halves).
  3. Two equal elements [3, 3] — True.
  4. All zeros — The problem forbids this (positive integers), but if allowed the answer is true.
  5. Large single element dominating total — [100, 1, 1]: total=102, target=51; no subset can hit 51 because 100 is too big and the others too small. False.
  • LC 494 — Target Sum: Assign +/- to each number to hit a target. Reduces to subset sum.
  • LC 474 — Ones and Zeroes: Two-dimensional knapsack.
  • LC 2035 — Partition Array Into Two Arrays to Minimize Sum Difference: Minimize |sumA - sumB| under size constraint.
  • LC 698 — Partition to K Equal Sum Subsets: Generalized to K partitions, requires backtracking + bitmask DP.

What Is Expected at Each Level? ​

Junior / New Grad: See that it reduces to subset sum. Might start with 2D DP; should simplify to 1D with a nudge.

Mid-level: Write the 1D DP directly, explain the descending iteration, and cover the odd-total shortcut.

Senior: Discuss bitset optimization (use a bitset<10001> to parallelize the inner loop — a classic competitive trick). Extend to K-partition and note that becomes NP-hard in the general case; discuss meet-in-the-middle for larger N.

Frontend interview preparation reference.