Skip to content

Volume ITechnology

4.23.12 — Partition Equal Subset Sum ​

LeetCode 416 · Medium

The problem ​

Return true if the array can be split into two subsets with equal sums.

[1,5,11,5]   →  true    ([1,5,5] and [11])
[1,2,3,5]    →  false

Up to 200 numbers, each at most 100.

Restating the Problem: You have a set of numbers. You need to divide them into two piles such that the sum of the numbers in the first pile is exactly equal to the sum of the numbers in the second pile.

Constraints to Note:

  • The array can have up to 200 elements.
  • Each element is up to 100.
  • This means the maximum possible sum of the entire array is 20,000, and the target half-sum is at most 10,000.

The brute force, and where it wastes work ​

The brute force method is to generate every possible subset of the array, compute its sum, and check if it equals exactly half of the total sum. Since each of the N items can either be in the subset or not, there are 2^N possible subsets. For N=200, 2^{200} is unfathomably huge. This exponential backtracking approach will instantly Time Limit Exceed. We must find a pseudo-polynomial DP approach.

The pattern ​

Two reductions, and the first one halves the problem.

Reduction 1. If the two halves have equal sums, each equals total / 2. So the question becomes: is there a subset summing to exactly total / 2? You never need to think about the second subset — whatever is left over is automatically the other half.

And if the total is odd, the answer is immediately false. That check costs one line and rejects a large fraction of inputs.

Reduction 2. "Is there a subset summing to exactly T" is the 0/1 knapsack decision problem — each item is either taken or not, and you want to hit a target exactly.

Enumerating all 2^n subsets is far too slow at n = 200. But the sums are bounded: at most 200 × 100 / 2 = 10,000. Bounded values mean a table indexed by value, and that is what makes it tractable.

Let dp[t] be true when some subset sums to exactly t.

The solution ​

python
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)  # (1)
        if total % 2:  # (2)
            return False                     # cannot split an odd total

        target = total # (3) 2
        dp = [False] * (target + 1)  # (4)
        dp[0] = True                         # (5) the empty subset sums to 0

        for n in nums:  # (6)
            for t in range(target, n - 1, -1):        # (7) DOWNWARDS — see below
                dp[t] = dp[t] or dp[t - n]  # (8)
            if dp[target]:  # (9)
                return True                  # early exit

        return dp[target]  # (10)
ts
function canPartition(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0);  // (1)
  if (total % 2) return false;  // (2)

  const target = total / 2;  // (3)
  const dp = new Array(target + 1).fill(false);  // (4)
  dp[0] = true;  // (5)

  for (const n of nums) {  // (6)
    for (let t = target; t >= n; t--) {  // (7)
      dp[t] = dp[t] || dp[t - n];  // (8)
    }
    if (dp[target]) return true;  // (9)
  }

  return dp[target];  // (10)
}

Line by line ​

(1) Add up all the numbers.

(2) An odd total cannot be split into two equal whole halves. total % 2 is 1 for an odd number, which counts as true.

(3) The question becomes: can some of the numbers add up to exactly half? If one group adds to half, the rest adds to the other half automatically.

(4) dp[t] will mean "some of the numbers seen so far add up to exactly t". All start as false.

(5) A sum of 0 is always possible: choose nothing.

(6) Consider each number once.

(7) Update every sum from target down to n. Going downward is essential, and the next section explains why.

(8) Sum t is reachable if it already was, or if t − n was reachable before this number, so that adding n lands on t.

(9) Stop as soon as half is reachable.

(10) Whether half can be reached.

The loop direction, which is the whole point ​

The inner loop counts downwards, and that is what stops an item being used twice.

Here is why. When you process item n and read dp[t - n], you want that value to describe subsets formed from the previous items only — not subsets that already include n.

  • Going downwards, dp[t - n] is at a lower index that has not been updated yet in this round, so it still holds the value from before this item. The item is used at most once. 0/1 knapsack.
  • Going upwards, dp[t - n] may already have been updated in this round to include n, so n gets used again. Unbounded knapsack.

One character of loop direction gives two completely different problems. This is the mistake named in 4.22, and it is why you should understand rolling arrays rather than copy them.

Compare directly:

python
# each item ONCE  (this problem)
for n in nums:
    for t in range(target, n - 1, -1): ...

# items REUSABLE  (Coin Change, 4.23.8)
for c in coins:
    for t in range(c, target + 1): ...

When you meet a DP whose loop runs backwards and you cannot see why, this is almost always the reason.

The other details ​

dp[0] = True — the empty subset sums to zero, and every other reachable sum is built from it.

range(target, n - 1, -1) stops at n, because below n the item cannot be used and dp[t - n] would index negatively.

The early exit is a real saving on inputs that reach the target quickly.

Trace ​

[1, 5, 11, 5], total 22, target 11.

itemsums now reachable
start{0}
1{0, 1}
5{0, 1, 5, 6}
11{0, 1, 5, 6, 11, ...} → dp[11] true → return true

The subset is [11], leaving [1, 5, 5] which also sums to 11 ✓.

Edge cases ​

  • An odd total. Line (2) returns false at once.
  • One number. It cannot be split into two non-empty equal groups, and the code returns false.
  • A number bigger than half. It can never be in the half-sum group, and the inner loop simply never reaches it.

The bitset trick ​

There is a one-line version that is dramatically faster in practice:

python
bits = 1                                     # bit t set means "sum t is reachable"
for n in nums:
    bits |= bits << n
return (bits >> (total // 2)) & 1 == 1

bits << n shifts every reachable sum up by n — that is, adds n to all of them at once — and |= merges the new sums with the old.

Python's unbounded integers make this legal, and the CPU processes 64 sums per machine word, so it is roughly 64 times faster than the loop with the same asymptotic bound. Know it, and write the explicit loop in an interview — the point of the question is the knapsack, and the bitset hides it.

Complexity ​

O(n \times \text{target}) time, which is O(n \times \text{sum}). With n = 200 and sums up to 10,000, that is 2 million operations.

O(\text{target}) space.

Time Complexity Derivation: We first calculate the sum of the array which takes O(n). Then we have an outer loop iterating n times. The inner loop iterates up to target times. Inside the loops we do a constant O(1) boolean OR operation. Total time is O(n) + O(n \times \text{target}) = O(n \times \text{target}).

Space Complexity Derivation: We allocate a single 1-D boolean array dp of size target + 1. So the auxiliary space is strictly O(\text{target}).

This is pseudo-polynomial, the same caveat as 4.23.8 Coin Change: polynomial in the value of the sum, not in the number of bits used to write it. The subset-sum problem is NP-complete in general, and this table only works because the values are small. Saying that out loud is a strong signal — it shows you know the difference between "I found a polynomial algorithm" and "the constraints let me get away with a table".

Where this goes next ​

  • Target Sum — assign + or − to each number to reach a target. It reduces to subset sum with the target (total + S) / 2, and deriving that reduction is the whole problem. 4.24.5.
  • Last Stone Weight II — minimise the difference between two groups, which is subset sum closest to total / 2.
  • Partition to K Equal Sum Subsets — much harder; needs backtracking with a bitmask of used items.
  • 0/1 knapsack with values — the same loop with max(dp[t], dp[t-w] + v) instead of or.

The four knapsack shapes, worth learning as a set: reachability (or), counting (+), maximising value (max), and unbounded versions of each — which differ only in the loop direction.

What the interviewer will push on ​

"How do you reduce this to one subset?" Equal halves each sum to total / 2, so finding one is enough.

"What if the total is odd?" Immediately false.

"Why does the inner loop go downwards?" So each item is used at most once. This is the question, and being able to explain both directions is what separates understanding from copying.

"What is the complexity, and is that polynomial?" O(n \times \text{sum}), pseudo-polynomial, and subset sum is NP-complete in general.

"Could you return the actual subset?" Keep the 2-D table instead of rolling it, then walk backwards asking at each item whether the sum was reachable without it.

One thing to volunteer: name it as 0/1 knapsack before writing anything, and say that the loop direction is what enforces the "0/1". That one sentence covers both the reduction and the easy-to-miss loop direction.

Next: 4.24 adds the second dimension — grids, two sequences compared, and the interval problems whose O(n^3) you can read straight off the state count.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet