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

Hiring now

Google has 52 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Small Business Field Sales Representative
Denver, Colorado
Senior Technical Program Manager, Special Projects
Denver, Colorado; Lakewood, Colorado, United States
OSP Engineering Lead, Technical Operations
Denver, Colorado

Or practice this question first

Next question