📖 5 min read
Last updated on

Partition Equal Subset Sum — Coding Interview Walkthrough

By intervu.dev

You’re in a coding interview. The interviewer says: “Given an array of positive integers, can you partition it into two subsets with equal sums?” If you recognize the reduction — “can any subset sum to total / 2?” — you’re halfway there. This is a 0/1 knapsack DP problem, and it rewards candidates who can identify the classic reduction, define the DP state cleanly, and implement the space-optimized 1D version.

The Problem

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

(LeetCode #416)

Example 1

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

Output true — partition into [1, 5, 5] and [11]

Example 2

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

Output false — no valid partition

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

SkillWhat Interviewers Observe
Problem reductionDo you reduce “equal partition” to “subset sum = total/2”?
0/1 knapsack DPDo you recognize and apply the classic pattern?
Space optimizationCan you reduce from 2D DP to 1D by iterating in reverse?
Early terminationDo you check for odd total and return false immediately?
State definitionCan you define dp[j] precisely: “can we form sum j from elements seen so far”?

Step 1: Clarifying Questions

1. Can elements be negative? No — the problem constrains nums[i] >= 1.

2. What if the total sum is odd? Return false immediately. Two equal-sum partitions require an even total.

3. What if the array has one element? A single element can’t be split into two non-empty subsets — return false.

4. Are elements bounded? 1 <= nums[i] <= 100 and 1 <= len(nums) <= 200. Target sum is at most 200 * 100 / 2 = 10000. The DP table is manageable.

Step 2: The Key Reduction

If the total sum is S:

  • For a valid partition, both halves must sum to S / 2.
  • So the question reduces to: can any subset of nums sum to S / 2?

This is the 0/1 knapsack subset sum problem.

Step 3: The Key Insight

Define dp[j] as True if some subset of elements seen so far sums to exactly j. For each new element num, updating in reverse order (from target down to num) ensures each element is used at most once. If dp[target] becomes True, the partition exists.

DP boolean array for nums=[1,5,11,5], target sum=11. dp[11]=True highlighted, showing which sums are achievable. ---

Step 4: Algorithm

  1. Compute total = sum(nums). If total % 2 != 0, return False.
  2. Set target = total // 2.
  3. Initialize dp = [False] * (target + 1). Set dp[0] = True (empty subset sums to 0).
  4. For each num in nums:
    • Iterate j from target down to num:
      • dp[j] = dp[j] or dp[j - num]
  5. Return dp[target].

Python Implementation

2D DP (easier to derive, then optimize):

def canPartition_2d(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    n = len(nums)

    # dp[i][j] = True if first i elements can sum to j
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = True  # empty subset always sums to 0

    for i in range(1, n + 1):
        num = nums[i - 1]
        for j in range(target + 1):
            dp[i][j] = dp[i - 1][j]  # don't include nums[i-1]
            if j >= num:
                dp[i][j] = dp[i][j] or dp[i - 1][j - num]  # include it

    return dp[n][target]

1D DP (space-optimized — what you should write in an interview):

def canPartition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2

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

    for num in nums:
        for j in range(target, num - 1, -1):  # iterate in reverse
            dp[j] = dp[j] or dp[j - num]
        if dp[target]:  # early exit
            return True

    return dp[target]

Time & Space Complexity

TimeSpace
2D DPO(n * target)O(n * target)
1D DPO(n * target)O(target)

target is at most sum(nums) / 2. With constraints, this is at most 10,000.

Common Interview Mistakes

  1. Iterating forward in the 1D DP. If you iterate j from num to target (increasing), you can use num multiple times in the same pass — that models the unbounded knapsack, not 0/1 knapsack. Reverse iteration enforces each element is used at most once.

  2. Forgetting dp[0] = True. The base case is that the empty subset has sum 0. Without this, no subset can ever be “built up” in the DP.

  3. Not handling odd totals early. Always check total % 2 != 0 before building the DP table. Saves unnecessary work and is a clear correctness check interviewers notice.

  4. Confusing subset sum with partition. The partition constraint means you don’t need to find which elements are in each half — just whether one subset summing to target exists. The other elements automatically form the complement.

What a Strong Candidate Sounds Like

“The key reduction: for a valid partition, both subsets sum to total / 2. So I just need to check if any subset sums to target = total / 2. This is 0/1 knapsack. I’ll use a 1D DP: dp[j] is true if some subset sums to j. For each element, I iterate j from target down to num — reverse order ensures each element is used at most once. Time is O(n * target), space is O(target).”

Example Interview Dialogue

Interviewer: Why iterate in reverse in the 1D DP?

Candidate: In the 0/1 knapsack, each element can be used at most once. In the 1D DP, dp[j] depends on dp[j - num] from the same row. If I iterate forward, by the time I compute dp[j], dp[j - num] has already been updated with the current element — so I might add the element again. Iterating backward ensures dp[j - num] still reflects the state before the current element was considered.

Interviewer: What’s the worst-case input size?

Candidate: len(nums) = 200, nums[i] = 100, so target is at most 10,000. The DP table is 200 * 10,000 = 2 million operations — fast and well within time limits.

  • Target Sum (LeetCode #494). Assign +/- to each element to reach a target — reduces to subset sum.
  • Last Stone Weight II (LeetCode #1049). Minimize the difference between two subset sums — same knapsack reduction.
  • Coin Change (LeetCode #322). Unbounded knapsack — compare with 0/1 knapsack to understand the forward/reverse iteration difference.
  • Subsets (LeetCode #78). Enumerate all subsets — complement to subset-sum DP.

Practice This in a Mock Interview

Partition Equal Subset Sum is the canonical 0/1 knapsack interview problem. The reduction to subset sum and the reverse-iteration trick in the 1D DP are the two things you need to lock in. If you can derive the 2D DP first and then optimize to 1D while explaining why the iteration direction changes, that’s an extremely strong answer.

Start a mock interview for Partition Equal Subset Sum on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →