MediumCoding

Partition equal subset sum

Asked at

Google

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array arr of n integers, return true if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal else return false.

**Input: **arr = [1, 10, 21, 10] Output: True Explanation: The array can be partitioned as [1, 10, 10] and [21].

**Input: **arr = [1, 2, 3, 5] **Output: **False Explanation: The array cannot be partitioned into equal sum subsets.

Input: arr = [2, 2, 1, 1]

1 ≤ n ≤ 100
1 ≤ arr[i] ≤ 1000
n*sum of elements ≤ 105

cpp

class Solution{
public:
    bool equalPartition(int n, vector<int> arr) {

    }
};

java

class Solution {
    public boolean equalPartition(int n, int[] arr) {
   
    }
}

python

class Solution:
    def equalPartition(self, n, arr):

javascript

class Solution {
    equalPartition(n, arr) {
      
    }
}

csharp

class Solution {
    public bool EqualPartition(int n, int[] arr) {
        
    }
}

func equalPartition(n int, arr []int) bool {

}

Solve on LeetCode →

Stuck? Show a way to structure it+

01Sum all values
02Reject odd totals
03Target half
04Update reachable sums backward
05Return target reachability

Reference answer

Reduce to one target

If total sum is odd, two equal subsets are impossible. Otherwise target total / 2. Maintain dp[s] meaning some subset of processed numbers has sum s; set dp[0] = true. For each number x, iterate s downward from target to x and set dp[s] |= dp[s-x]. Backward iteration is essential: it ensures x is used at most once.

After all numbers, dp[target] answers the question. Time is O(n * target) and space is O(target). A two-dimensional table is a transparent O(n * target)-space baseline; use it if reconstruction is required. Test odd total, one number, repeated numbers, a target reached only by several values, and zeros. Clarify that standard inputs are nonnegative; negative values invalidate this bounded-sum state without an offset or different formulation. Do not confuse this with unbounded coin change, where forward iteration is appropriate.

Then expect these follow-ups

Why must sums be updated backward?
Tests: correctness reasoning
How would you reconstruct a subset?
Tests: implementation extension

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question