Skip to main content

416. Partition Equal Subset Sum

medium

Can the array be split into two subsets with equal sum? Reduces to subset-sum = total/2 — a textbook 0/1 knapsack as a boolean 1D DP.

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

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.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If total is odd return false immediately.

Hint 2

Otherwise the question becomes: can a subset sum to total/2? Classic 0/1 knapsack feasibility.

Hint 3

Use a 1D boolean dp of size target+1. Iterate items as outer loop, target descending as inner.

Solution approach

Reveal approach

Compute total = sum(nums). If total is odd return false. Set target = total / 2. The problem reduces to: does any subset of nums sum exactly to target? Use a 1D boolean dp where dp[s] is true if some subset sums to s. Initialize dp[0] = true. For each num in nums, sweep s from target down to num and set dp[s] = dp[s] OR dp[s - num]. The reverse loop direction matters — it ensures each num is used at most once (0/1 knapsack semantics). Return dp[target]. O(n * target) time, O(target) space.

Complexity

Time
O(n * sum/2)
Space
O(sum/2)

Related patterns

  • dynamic-programming
  • knapsack-0-1

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Facebook

Practice these live with InterviewChamp.AI

Drill Partition Equal Subset Sum and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →