Skip to main content

15. Partition Equal Subset Sum

mediumAsked at JetBrains

Decide whether an array can be split into two equal-sum subsets — JetBrains uses this to test subset-sum DP space optimization, a primitive in their refactor cost balancing.

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 with equal sum. Otherwise return false.

Constraints

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

Examples

Example 1

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

Example 2

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

Approaches

1. Subset enumeration

Try every subset and check if its sum equals total/2; exponential.

Time
O(2^n)
Space
O(n)
// branch include/exclude on each index, prune when sum exceeds half — still exponential worst case

Tradeoff:

2. 1D bit-DP

Reduce to subset-sum target = total/2. Use a boolean array dp where dp[s] = is s reachable, updated in reverse to avoid reuse. Same compact DP shape JetBrains refactor-cost balancers use.

Time
O(n * sum)
Space
O(sum)
function canPartition(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2) return false;
  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const n of nums) {
    for (let s = target; s >= n; s--) dp[s] = dp[s] || dp[s - n];
  }
  return dp[target];
}

Tradeoff:

JetBrains-specific tips

JetBrains expects you to explain why the inner loop iterates in reverse — they grade for understanding why DP state updates must respect dependency direction, the same discipline as evaluating dataflow attributes in topological order.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →