Partition Equal Subset Sum

MediumDynamic Programming0/1 knapsack

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given an array of positive integers nums, determine whether it can be split into two subsets whose elements add up to the same total. Every element must belong to exactly one of the two subsets (you cannot leave any element out or use it twice). The subsets do not need to be the same size or contiguous, and either subset may be chosen freely from any positions in the array. Return true if such a partition exists, and false otherwise. For example, [1, 5, 11, 5] can be divided into [1, 5, 5] and [11], both summing to 11, so the answer is true. In contrast, [1, 2, 3, 5] has total 11, which is odd, so no equal split is possible and the answer is false.

Examples

Input: nums = [1, 5, 11, 5]
Output: true
The array can be partitioned into [1, 5, 5] and [11], each summing to 11.
Input: nums = [1, 2, 3, 5]
Output: false
The total is 11, which is odd, so it cannot be divided into two equal halves.
Input: nums = [2, 2, 2, 2]
Output: true
Split into [2, 2] and [2, 2], each summing to 4.

Constraints

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100
  • The sum of all elements does not exceed 20000.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 0/1 knapsack problems