Skip to main content

416. Partition Equal Subset Sum

mediumAsked at DoorDash

Return true if the array can be partitioned into two subsets with equal sums. DoorDash uses this as a 0/1 knapsack disguised as a partition problem — they want the bottom-up DP that uses a boolean array.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports list Partition Equal Subset Sum as a recurring DP question.
  • Blind (2025-11)— DoorDash new-grad reports cite this for backend rounds.

Problem

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Constraints

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

Examples

Example 1

Input
nums = [1,5,11,5]
Output
true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2

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

Explanation: The array cannot be partitioned into equal sum subsets.

Approaches

1. 1D bottom-up DP (optimal space)

If total is odd, return false. Else target = total/2. dp[s] = can we reach sum s? Iterate items; for each, update dp from high to low.

Time
O(n * target)
Space
O(target)
function canPartition(nums) {
  let total = 0;
  for (const x of nums) total += x;
  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];
}

Tradeoff: DoorDash's expected answer. The high-to-low inner loop prevents double-counting an item. Pure 0/1 knapsack — name this aloud.

2. Top-down memoization

Recurse: f(i, s) = can we hit s using nums[i:]? Memoize on (i, s).

Time
O(n * target)
Space
O(n * target)
function canPartitionTopDown(nums) {
  let total = 0;
  for (const x of nums) total += x;
  if (total % 2 !== 0) return false;
  const target = total / 2;
  const memo = new Map();
  function dfs(i, s) {
    if (s === 0) return true;
    if (s < 0 || i === nums.length) return false;
    const key = i + '_' + s;
    if (memo.has(key)) return memo.get(key);
    const result = dfs(i + 1, s - nums[i]) || dfs(i + 1, s);
    memo.set(key, result);
    return result;
  }
  return dfs(0, target);
}

Tradeoff: Same complexity but uses O(n * target) memo. Mention as the natural recursion shape — but ship the 1D version.

DoorDash-specific tips

DoorDash interviewers grade on the KNAPSACK FRAMING. State 'this is 0/1 knapsack on target = total/2' before coding. The HIGH-TO-LOW inner loop is the bug surface — explain that loop direction prevents reusing the same item twice.

Common mistakes

  • Iterating the inner loop low-to-high — counts the same item multiple times (turning 0/1 into unbounded knapsack).
  • Forgetting the odd-total early exit.
  • Using O(n * target) 2D space when 1D suffices.

Follow-up questions

An interviewer at DoorDash may pivot to one of these next:

  • Target Sum (LC 494) — assign +/- to each item to reach a target.
  • Last Stone Weight II (LC 1049) — minimize difference between two subset sums.
  • Partition to K Equal Sum Subsets (LC 698) — generalization to k subsets.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why high-to-low in the inner loop?

To use each item at most once. If we went low-to-high, dp[s] = dp[s - num] would already reflect THIS item, double-counting it.

What's the target?

total / 2 (when total is even). If total is odd, no equal partition is possible.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Partition Equal Subset Sum and other DoorDash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →