What is the brute force approach and complexity for Partition Equal Subset Sum?

Take or skip each number; succeed if some subset reaches total / 2 with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Partition Equal Subset Sum?

One true / false row over sums 0 … total / 2; each number updates it from high to low with optimal time complexity O(N · S) and space complexity O(S).

How do you identify the pattern for Partition Equal Subset Sum?

Look for key signals in the prompt: "split into two groups with equal sums" indicates Each group must reach total / 2. Find one subset with that sum, and the other group is what is left.; "every number goes into exactly one group" indicates Each number is taken or skipped at most once → 0/1 knapsack, not unbounded.; "return true or false" indicates We only need to know whether the target can be reached, so one row of true / false values is enough..

Partition Equal Subset Sum

Medium·LeetCode #416Basic Anchor

LeetCode

Jump:

30-Second Mental ModelKnapsack — 0/1 subset sum (partition into two groups)

Complexity:O(2^N)→O(N · S)

Key Insight

Keep one row dp[s]: can some of the numbers seen so far add up to s? Start with only dp[0] = true. For each number x, go from s = half down to x and set dp[s] = dp[s] || dp[s − x]. Going high → low means dp[s − x] still holds the value from before x was added, so x is never used twice.

Core Validity Invariant

Two equal groups exist exactly when some subset adds up to total / 2, and dp[half] records whether one does.

Problem

You get a list of positive whole numbers, nums. Can you split the list into two groups so that both groups have the same sum?

Every number goes into exactly one of the two groups. Return true if an equal split is possible, and false if it is not.

Input

An array of positive integers nums.

Output

true if the numbers can be split into two groups with equal sums, otherwise false.

Example 1

Input: nums = [1, 5, 11, 5]

Output: true

Put 1, 5 and 5 in one group (sum 11). The other group is [11], which also sums to 11.

Example 2

Input: nums = [1, 2, 3, 5]

Output: false

The total is 11, which is odd. Two equal groups would each need a sum of 5.5, and that is not a whole number.

Example 3

Input: nums = [3, 3, 2, 2, 2]

Output: true

Put the two 3s in one group (sum 6). The three 2s make the other group, which also sums to 6.

Constraints

• 1 ≤ nums.length ≤ 200
• 1 ≤ nums[i] ≤ 100

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If the two groups must be equal, what must each group add up to? Can I work that out from the total alone?
2.
If the total is odd, can two groups with equal sums exist? What goes wrong?
3.
Each number goes in group A or group B. Is that the same kind of choice I make for every number in a subset problem?
4.
If one group adds up to the target, what do I know about the other group? Do I need to check it separately?
5.
Would the rule 'always add the next number to the lighter group' always give the right answer? Try [3, 3, 2, 2, 2] by hand.

Brute force approach

Idea

If the total is odd, the answer is false. Otherwise each group must add up to total / 2. So we only need one subset that sums to total / 2. The other group is whatever is left, and it sums to the same amount. The brute force tries every subset: for each number it takes it or skips it, and it stops a path when the sum goes too high.

Thinking process

1
Two equal groups must each add up to total / 2. For [1, 5, 11, 5] the total is 22, so each group needs 11.
2
I only need one subset that adds up to 11. Whatever is left over is the other group.
3
Ask about the first number, 1: take it (now I need 10) or skip it (I still need 11). Each choice leads to a new question for the next number.
4
Take 1, then take 5 (need 5). Taking 11 would leave need −6, which is a dead end, so skip it. Then take 5: need 0. So [1, 5, 5] is one half.
5
A path ends in three ways: the need is exactly 0 (success), the need drops below 0 (too big), or the numbers run out.

Visual

Each call asks: can some numbers from index i on add up to need? Purple = need 0 (found). Red = dead end (need below 0, or no numbers left). Orange = the same (i, need) as an earlier call; a table would answer it once. Blue = the path from the top to this call.

Brute force asks the same question againnums = [1, 1, 4] (total 6, half 3)step 1/16

tree

nums

▲i

taken

Calls so far (i, need)

(0, 3)

State

i: 0
need: 3
half: 3

Can we reach 3 from nums[0] = 1 on?

Take 1 (need 2) first, then skip it (need stays 3).

Code & Implementation

brute.cpp

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 != 0) return false;   // an odd total can't split into two equal whole sums
        return canReach(nums, 0, total / 2);
    }

private:
    // Can some subset of nums[i..] add up to exactly `need`?
    // Each number is taken or skipped, so this tries every subset.
    bool canReach(vector<int>& nums, int i, int need) {
        if (need == 0) return true;
        if (need < 0 || i == (int)nums.size()) return false;
        return canReach(nums, i + 1, need - nums[i]) || canReach(nums, i + 1, need);
    }
};

Complexity

Time O(2^N)Space O(N)

N is the number of numbers. Each number is taken or skipped, so there can be up to 2^N paths. The recursion is at most N calls deep, which is the space. With N = 200 this is far too slow.

Better approach

Why brute force is slow

The brute force explores every path on its own, so the work grows with the number of paths (up to 2^N). Yet there are only (N + 1) × (total / 2 + 1) different questions.

What repeated work are we doing?

The same question, 'with sum s still to make after i numbers', is reached by different paths. In the [1, 1, 4] example, two paths both ask 'can we make 2 from the 4 onward?'

What information can we reuse?

Store every answer once in a table. Row i reads only row i − 1, so each cell is one O(1) lookup, and no question is answered twice.

New approach

Idea

The brute force asks the same question again and again: can we reach sum s using only the first i numbers? Store each answer once in a table dp[i][s]. Row i uses the first i numbers, and column s is a sum from 0 to total / 2. Each cell is filled in O(1) from the row above it: skip the number, or take it.

Thinking process

1
The brute force repeats questions. On [1, 1, 4] with half = 3, one path takes the first 1 and then skips the second. Another path skips the first 1 and takes the second. Both leave need 2 with only the 4 left to use.
2
A table answers each question once. Row i means 'the first i numbers' and column s means 'the sum'. dp[i][s] = T if some of those numbers add up to s.
3
Take [2, 3, 3, 4] with half = 6. Row 1 (only 2): sums 0 and 2 are T. Row 2 (add 3): sums 0, 2, 3 and 5 are T. dp[2][5] = T because dp[1][2] is T and 2 + 3 = 5.
4
Row 4 (add 4) gives dp[4][6] = T, because dp[3][2] is T and 2 + 4 = 6. So the answer is true, with the groups {2, 4} and {3, 3}.

Visual

Row i = the first i numbers (row 0 = none), column s = the sum. T = some of those numbers add up to s, F = none. Each new cell reads the cell above (skip) and, when the number fits, the cell above it shifted left by the number (take). Blue = the cells read, green = T, purple = the answer.

The 2-D table of reachable sumsnums = [2, 3, 3, 4] (total 12, half 6)step 1/30

dp[i][s]

nums

State

row: 0 (no numbers)
reachable sums: 0

Row 0: no numbers, so only sum 0 is reachable

Row 0 is the empty set. It makes sum 0 and nothing else, so dp[0][0] = T and the other cells in row 0 are F.

Code & Implementation

better.cpp

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 != 0) return false;
        int half = total / 2;

        // dp[i][s] = true if some subset of the first i numbers adds up to s.
        vector<vector<bool>> dp(n + 1, vector<bool>(half + 1, false));
        for (int i = 0; i <= n; i++) dp[i][0] = true;   // the empty subset adds up to 0

        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            for (int s = 1; s <= half; s++) {
                dp[i][s] = dp[i - 1][s];                          // leave nums[i-1] out
                if (s >= x) dp[i][s] = dp[i][s] || dp[i - 1][s - x];   // or put it in
            }
        }
        return dp[n][half];
    }
};

Complexity

Time O(N · S)Space O(N · S)

S = total / 2, the target sum. The table has N + 1 rows and S + 1 columns, and each cell takes O(1) work. With values up to 100 and N up to 200, S can reach 10000, so the table can hold about 2 million cells.

Optimized approach

Idea

Start from brute force

The brute force takes or skips every number, so it looks at every subset, up to 2^N of them, just to find one that sums to half.

Find the repeated work

Many different subsets reach the same sum with the same numbers left. The question 'can this sum still be made?' is asked again on every path that gets there.

Define the state — what variables do I need?

dp: dp[s] = true when some of the numbers processed so far add up to s.
half: The target, total / 2. It is only used when the total is even.
x: The number being added in the current round of the loop.

Define validity

Two equal groups exist exactly when some subset adds up to total / 2, and dp[half] records whether one does.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

If the total is odd, return false. Otherwise half = total / 2 and dp[0] = true.

An odd total can never split into two equal whole sums. The empty subset adds up to 0, so dp[0] starts as true.

For each number x, with s from half down to x

dp[s] = dp[s] || dp[s − x]

dp[s − x] still holds the value from before x, so x is never used twice.

After all the numbers

return dp[half]

dp[half] is true exactly when some subset adds up to half, and then the rest of the numbers add up to half too.

What does the current window add to the answer?

Each number adds the sums it can create: every s whose dp[s − x] is true becomes reachable. At the end, only dp[half] is read.

Code & Implementation

optimal.cpp

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 != 0) return false;
        int half = total / 2;

        // dp[s] = true if some subset of the numbers seen so far adds up to s.
        vector<bool> dp(half + 1, false);
        dp[0] = true;   // the empty subset adds up to 0

        for (int x : nums) {
            // Go high → low: dp[s - x] still holds the value from before this number,
            // so this number is never used twice.
            for (int s = half; s >= x; s--) {
                dp[s] = dp[s] || dp[s - x];
            }
        }
        return dp[half];
    }
};

Complexity

Time O(N · S)Space O(S)

N is the number of numbers and S = total / 2. Each number scans at most S + 1 cells of the one row, instead of filling N + 1 rows as the table does. The answers are the same.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Take or skip each number; succeed if some subset reaches total / 2	O(2^N)	O(N)
Better	dp[i][s] = can the first i numbers make sum s? Fill it row by row	O(N · S)	O(N · S)
Optimal	One true / false row over sums 0 … total / 2; each number updates it from high to low	O(N · S)	O(S)

Why does this belong to this pattern?

Clues in the problem statement

“split into two groups with equal sums”Each group must reach total / 2. Find one subset with that sum, and the other group is what is left.
“every number goes into exactly one group”Each number is taken or skipped at most once → 0/1 knapsack, not unbounded.
“return true or false”We only need to know whether the target can be reached, so one row of true / false values is enough.

split into two equal-sum groups+one subset with sum total / 2+each number used at most once→Knapsack — 0/1 subset sum (partition into two groups)

This is the anchor of the Partition sub-pattern. The key step is the reduction: two equal groups exist exactly when one subset sums to total / 2, because the other group is whatever is left. An odd total gives false at once, since no whole number is half of it. After that it is plain 0/1 subset sum: each number is used once, so the row is filled high → low. Unlike the Subset Sum questions in the 0/1 sub-pattern, the target is not given. You compute it from the total, so check the total first.

Don't make this mistake

Pattern confusion: the greedy 'lighter group' rule

✗ sort nums from largest to smallest; for (int x : nums) { if (a <= b) a += x; else b += x; } return a == b;

✓ bool dp row over sums 0 … half; return dp[half];

The greedy looks reasonable, but it commits to each number before it has seen the rest. On the dry-run input [3, 3, 2, 2, 2] (total 12, so each group needs 6) it does: 3 → A, 3 → B, 2 → A (5 vs 3), 2 → B (5 vs 5), 2 → A (7 vs 5). It returns false. The answer is true, because [3, 3] and [2, 2, 2] each sum to 6. The table finds it, because dp[6] is set by 3 + 3 before the 2s are even considered.

Forgetting the odd check

✗ int half = total / 2; // no odd check, so 11 / 2 = 5

✓ if (total % 2 != 0) return false;

On [1, 2, 3, 5] the total is 11, and 11 / 2 = 5 in integer division. The subset [5] sums to 5, so the DP returns true. But an odd total can never split into two equal whole sums, so the answer is false.

Filling the row low → high

✗ for (int s = x; s <= half; s++) dp[s] = dp[s] || dp[s - x];

✓ for (int s = half; s >= x; s--) dp[s] = dp[s] || dp[s - x];

On [1, 4, 1] the total is 6 and half is 3. Going low → high lets the first 1 be reused: dp[1] = T, then dp[2] = dp[1] = T (1 + 1), then dp[3] = dp[2] = T (1 + 1 + 1). It returns true, but the list has only two 1s, so no group sums to 3 and the answer is false.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Knapsack translate into production architectures and low-level memory mechanics.

LLD Architecture