Skip to main content

416. Partition Equal Subset Sum

medium

Determine whether an array can be partitioned into two subsets with equal sum. Recursion plus memoization solves it; the cleaner 0/1 knapsack DP is what production code ships.

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 sum is odd, return false immediately.

Hint 2

Target = sum / 2. The question reduces to 'is there a subset summing to target?'

Hint 3

Recurse: canMake(index, remaining) = canMake(index + 1, remaining) OR canMake(index + 1, remaining - nums[index]).

Hint 4

Memoize on (index, remaining). Or use the iterative 1D bool DP that loops nums outer and remaining inner (descending).

Solution approach

Reveal approach

Compute total sum. If sum is odd, return false. Let target = sum / 2. Goal: does some subset sum to target? Recursive approach: canMake(i, remaining): if remaining == 0 return true; if i == n or remaining < 0 return false. Return canMake(i + 1, remaining) OR canMake(i + 1, remaining - nums[i]). Memoize the result. Iterative DP: 1D boolean array dp of size target + 1, dp[0] = true. For each num in nums, for remaining from target down to num (descending crucial — prevents reusing the same element): dp[remaining] = dp[remaining] OR dp[remaining - num]. Return dp[target]. Time is O(n * target); space O(target).

Complexity

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

Related patterns

  • recursion
  • memoization
  • dynamic-programming
  • 0-1-knapsack

Related problems

Asked at

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

  • Amazon
  • Meta
  • Google

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →