DSA-138 · FOCUSED PRACTICE

Partition Equal Subset Sum

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 21868 deterministic checks. Learner drafts are not executed.

Understand the problem

Return whether all nums occurrences can be split into two disjoint subsets with equal total sum. Each occurrence must belong to exactly one subset, and either subset may be empty.

nums is a non-null int[] with at most 200 entries, each in 0..1000. Null throws NullPointerException; excessive length, negatives, or larger entries throw IllegalArgumentException. Validate every occurrence before any parity shortcut.
Equal values at different indices are distinct usable occurrences; do not deduplicate them. Each occurrence can be selected at most once for the target subset. All unselected occurrences form the other subset, so none is discarded.
Return a boolean and preserve input order and values. Empty input and all-zero arrays return true under the explicit empty-subset convention. Total is at most 200000 and target at most 100000, so int arithmetic for sums is exact. The recursive baseline is limited to small inputs.

Examples

Input: nums=[1,5,11,5]
Output: true
Select the 11 occurrence; the complement 1+5+5 also totals 11.
Input: nums=[1,2,3,5]
Output: false
The total is odd, so equal integer totals are impossible.
Input: nums=[1,2,5]
Output: false
The total is eight, but no subset of distinct occurrences sums to four.
Input: nums=[]
Output: true
Two empty subsets both sum to zero.

Before you start

Complement subsets and parity of a total
Occurrence ownership versus reusable denomination values

Recognize the structure

Choosing one side determines the other by complement. Equal sums are possible exactly when total is even and some subset sums to total/2. The state is existence of an exact sum using processed occurrences, not minimum count or unrestricted coin combinations. The crucial resource constraint is one use of each index, which determines the direction of an in-place amount scan.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 122/20,000 characters

Self-review

I can prove the complement reduction and state the empty-group convention.I can explain why both transition branches must read the previous occurrence layer.I can handle zeros, preserve duplicates, and identify pseudo-polynomial cost.

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

If one side totals T, what must the complement total?

Hint 2

Use a boolean exact-sum table for processed occurrences, not reusable types.

Hint 3

Read the previous occurrence layer in place by scanning target sums downward.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Select or omit each occurrence recursively

After full validation and parity checking, recursively skip the next index or take it if its value fits the remaining target. Reaching remaining zero succeeds; reaching the end with positive remaining fails. Even zero-valued choices advance the index, so recursion terminates. The search has O(2^n) upper-bound time and O(n+1) stack depth. Tests restrict it to small arrays and use a separate bit-mask oracle that explicitly assigns selected indices and compares their sum with the complement.

Improve the baseline

Reduce equality to one exact target

Let S be the total. If S is odd, return false. Otherwise a selected subset of sum T=S/2 has a complement of sum S−T=T, proving the equivalence in both directions. Selecting target zero is allowed; the API does not impose two nonempty groups.

Define the full occurrence-layer state

R(k,s) means some subset of the first k occurrences sums exactly to s. R(0,0)=true and R(0,s>0)=false. For value v at occurrence k, R(k,s)=R(k−1,s) OR R(k−1,s−v) when s≥v. Both alternatives must read the previous occurrence layer.

Compress by scanning amounts downward

Initialize reachable[0]=true. For each value v, scan amount from T down to v, OR-ing reachable[amount−v] into reachable[amount]. Because the smaller predecessor has not yet been updated for this occurrence, it still belongs to the old layer. An ascending scan would permit the same occurrence to feed itself repeatedly.

Understand duplicates, zeros, and parity

Two equal values provide two occurrences and can be chosen separately, so deduplication changes the problem. A zero creates a self-OR and no new reachable sums; the finite descending loop still visits each amount once. Compute and validate the entire total before returning false for odd parity.

Read a false instance that exposes loop direction

For [1,2,5], T=4. After the single 1, only 0 and 1 are reachable. An ascending scan would incorrectly produce 2,3,4 by reusing that same index. The descending scan prevents this and correctly returns false after all occurrences.

Why it is correct

Base layer and reduction

The empty selection realizes sum zero. No positive sum is possible before any occurrence. For an even total, any target-sum selection gives a valid equal-sum complement, and any equal partition supplies such a selection.

0/1 transition correctness

Every subset of a processed prefix either omits its newest occurrence or includes it once. Removing that occurrence in the latter case leaves a subset of the previous prefix totaling s−v. These alternatives are sound and exhaustive. Descending order ensures the implementation reads exactly that old prefix layer, not a state already using the same index.

Termination and output

Both occurrence and amount loops are finite, including v=0 because amount still decreases. After every occurrence, the boolean table equals the complete conceptual layer. The final target entry therefore answers the original partition question; odd totals have already been correctly rejected.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.Objects;

public final class Solution {
    private Solution() {}
    private static int total(int[] nums) {
        Objects.requireNonNull(nums, "nums");
        if (nums.length > 200) throw new IllegalArgumentException("too many occurrences");
        int total = 0;
        for (int value : nums) {
            if (value < 0 || value > 1_000) throw new IllegalArgumentException("value must be 0..1000");
            total += value;
        }
        return total;
    }
    public static boolean canPartition(int[] nums) {
        int sum = total(nums);
        if ((sum & 1) != 0) return false;
        int target = sum / 2;
        boolean[] reachable = new boolean[target + 1];
        reachable[0] = true;
        for (int value : nums) {
            for (int amount = target; amount >= value; amount--) reachable[amount] |= reachable[amount - value];
        }
        return reachable[target];
    }
    // Baseline: select or omit each physical occurrence. Small inputs only.
    public static boolean baseline(int[] nums) {
        int sum = total(nums);
        return (sum & 1) == 0 && select(nums, 0, sum / 2);
    }
    private static boolean select(int[] nums, int index, int remaining) {
        if (remaining == 0) return true;
        if (index == nums.length) return false;
        return select(nums, index + 1, remaining) || nums[index] <= remaining && select(nums, index + 1, remaining - nums[index]);
    }
}

Read the meaningful blocks

Validate and sum safely

total enforces length/value bounds before returning S. Since S≤200000, no wider sum is required here. A late invalid value cannot be hidden by an early parity result.

Initialize exact-sum reachability

Only sum zero starts true. There is no unreachable numeric sentinel and no count to add. Allocating T+1 entries includes both boundary sums zero and T.

Consume one occurrence per descending scan

The outer loop preserves physical occurrence supply, even for equal values. The inner OR reads a not-yet-updated smaller state. Returning a boolean does not retain a witness or tell which occurrences belonged to either side.

Complexity

Let n be occurrence count and T=S/2 for an even total. Validation is O(n+1), and the reference uses O(n(T+1)+1) time in the worst case and O(T+1) auxiliary boolean entries. Odd totals return after validation with O(1) extra storage. Output is one boolean.

This is pseudo-polynomial in the numeric target, rather than polynomial in its binary encoding length. The baseline takes O(2^n) upper-bound time and O(n+1) stack space. Returning one partition needs predecessor/choice history or a separately justified reconstruction method; the boolean row alone is not a chosen index set.

Exact-state walkthroughs

Reveal normal and boundary traces

Descending updates prevent occurrence reuse

Input: [1,2,5] · Equal occurrence partition exists: false

Step 1 of 23: Validate all occurrences and compute the complete total.

The bounded total fits int. For an even total, only sum zero starts reachable. Equal-valued indices remain separate physical occurrences.

Equal partition — one-use occurrences and descending sums

Phase: initial.

Original occurrences: [1,2,5]. Total=8. Target=4; a target subset and its complement have equal sums.

Live exact-sum reachability

0: trueexact-sum state
1: falseexact-sum state
2: falseexact-sum state
3: falseexact-sum state
4: falseexact-sum state

A smaller predecessor has not yet consumed this occurrence. Ascending updates would allow repeated use of the same index. A zero value only self-ORs and creates no new sums. Empty groups are allowed, so target zero is reachable by the empty subset.

All source values stay unchanged. Full grids, old layers and history cards explain state meaning; they do not add to Java reference workspace. Exact counts and products use decimal strings in trace data.

State after this step
Variable	Value
input	`[1,2,5]`
phase	`"initial"`
total	`8`
target	`4`
reachable	`[true,false,false,false,false]`
previous	`null`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static int total(int[] nums) {
 6         Objects.requireNonNull(nums, "nums");
 7         if (nums.length > 200) throw new IllegalArgumentException("too many occurrences");
 8         int total = 0;
 9         for (int value : nums) {
10             if (value < 0 || value > 1_000) throw new IllegalArgumentException("value must be 0..1000");
11             total += value;
12         }
13         return total;
14     }
15     public static boolean canPartition(int[] nums) {
16         int sum = total(nums);
17         if ((sum & 1) != 0) return false;
18         int target = sum / 2;
19         boolean[] reachable = new boolean[target + 1];
20         reachable[0] = true;
21         for (int value : nums) {
22             for (int amount = target; amount >= value; amount--) reachable[amount] |= reachable[amount - value];
23         }
24         return reachable[target];
25     }
26     // Baseline: select or omit each physical occurrence. Small inputs only.
27     public static boolean baseline(int[] nums) {
28         int sum = total(nums);
29         return (sum & 1) == 0 && select(nums, 0, sum / 2);
30     }
31     private static boolean select(int[] nums, int index, int remaining) {
32         if (remaining == 0) return true;
33         if (index == nums.length) return false;
34         return select(nums, index + 1, remaining) || nums[index] <= remaining && select(nums, index + 1, remaining - nums[index]);
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate all occurrences and compute the complete total.
The bounded total fits int. For an even total, only sum zero starts reachable. Equal-valued indices remain separate physical occurrences.
input
[1,2,5]
phase
"initial"
total
8
target
4
reachable
[true,false,false,false,false]
previous
null
Begin one physical occurrence layer.
Both transition alternatives must use this old layer. The saved row is explanatory; Java relies on descending order instead of cloning it.
input
[1,2,5]
phase
"item-start"
total
8
target
4
reachable
[true,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false]
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,2,5]
phase
"candidate"
total
8
target
4
reachable
[true,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false]
amount
4
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,2,5]
phase
"commit"
total
8
target
4
reachable
[true,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false]
amount
4
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,2,5]
phase
"candidate"
total
8
target
4
reachable
[true,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false]
amount
3
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,2,5]
phase
"commit"
total
8
target
4
reachable
[true,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false]
amount
3
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,2,5]
phase
"candidate"
total
8
target
4
reachable
[true,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false]
amount
2
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,2,5]
phase
"commit"
total
8
target
4
reachable
[true,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false]
amount
2
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,2,5]
phase
"candidate"
total
8
target
4
reachable
[true,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false]
amount
1
before
false
predecessor
true
next
true
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,2,5]
phase
"commit"
total
8
target
4
reachable
[true,true,false,false,false]
index
0
value
1
previous
[true,false,false,false,false]
amount
1
before
false
predecessor
true
next
true
This occurrence layer is complete.
Every amount now describes subsets of the complete processed prefix, including the current occurrence. No deduplication of equal values is permitted.
input
[1,2,5]
phase
"item-complete"
total
8
target
4
reachable
[true,true,false,false,false]
index
0
value
1
previous
[true,false,false,false,false]
Begin one physical occurrence layer.
Both transition alternatives must use this old layer. The saved row is explanatory; Java relies on descending order instead of cloning it.
input
[1,2,5]
phase
"item-start"
total
8
target
4
reachable
[true,true,false,false,false]
index
1
value
2
previous
[true,true,false,false,false]
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,2,5]
phase
"candidate"
total
8
target
4
reachable
[true,true,false,false,false]
index
1
value
2
previous
[true,true,false,false,false]
amount
4
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,2,5]
phase
"commit"
total
8
target
4
reachable
[true,true,false,false,false]
index
1
value
2
previous
[true,true,false,false,false]
amount
4
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,2,5]
phase
"candidate"
total
8
target
4
reachable
[true,true,false,false,false]
index
1
value
2
previous
[true,true,false,false,false]
amount
3
before
false
predecessor
true
next
true
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,2,5]
phase
"commit"
total
8
target
4
reachable
[true,true,false,true,false]
index
1
value
2
previous
[true,true,false,false,false]
amount
3
before
false
predecessor
true
next
true
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,2,5]
phase
"candidate"
total
8
target
4
reachable
[true,true,false,true,false]
index
1
value
2
previous
[true,true,false,false,false]
amount
2
before
false
predecessor
true
next
true
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,2,5]
phase
"commit"
total
8
target
4
reachable
[true,true,true,true,false]
index
1
value
2
previous
[true,true,false,false,false]
amount
2
before
false
predecessor
true
next
true
This occurrence layer is complete.
Every amount now describes subsets of the complete processed prefix, including the current occurrence. No deduplication of equal values is permitted.
input
[1,2,5]
phase
"item-complete"
total
8
target
4
reachable
[true,true,true,true,false]
index
1
value
2
previous
[true,true,false,false,false]
Begin one physical occurrence layer.
Both transition alternatives must use this old layer. The saved row is explanatory; Java relies on descending order instead of cloning it.
input
[1,2,5]
phase
"item-start"
total
8
target
4
reachable
[true,true,true,true,false]
index
2
value
5
previous
[true,true,true,true,false]
This occurrence layer is complete.
Every amount now describes subsets of the complete processed prefix, including the current occurrence. No deduplication of equal values is permitted.
input
[1,2,5]
phase
"item-complete"
total
8
target
4
reachable
[true,true,true,true,false]
index
2
value
5
previous
[true,true,true,true,false]
Read half-total reachability and use the complement.
A target subset and its unselected complement have equal totals. Empty groups are allowed, so an empty or all-zero input is true.
input
[1,2,5]
phase
"complete"
total
8
target
4
reachable
[true,true,true,true,false]
previous
null
Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
result
false

A reachable half total

Input: [1,5,11,5] · Equal occurrence partition exists: true

Step 1 of 63: Validate all occurrences and compute the complete total.

The bounded total fits int. For an even total, only sum zero starts reachable. Equal-valued indices remain separate physical occurrences.

Equal partition — one-use occurrences and descending sums

Phase: initial.

Original occurrences: [1,5,11,5]. Total=22. Target=11; a target subset and its complement have equal sums.

Live exact-sum reachability

0: trueexact-sum state
1: falseexact-sum state
2: falseexact-sum state
3: falseexact-sum state
4: falseexact-sum state
5: falseexact-sum state
6: falseexact-sum state
7: falseexact-sum state
8: falseexact-sum state
9: falseexact-sum state
10: falseexact-sum state
11: falseexact-sum state

State after this step
Variable	Value
input	`[1,5,11,5]`
phase	`"initial"`
total	`22`
target	`11`
reachable	`[true,false,false,false,false,false,false,false,false,false,false,false]`
previous	`null`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static int total(int[] nums) {
 6         Objects.requireNonNull(nums, "nums");
 7         if (nums.length > 200) throw new IllegalArgumentException("too many occurrences");
 8         int total = 0;
 9         for (int value : nums) {
10             if (value < 0 || value > 1_000) throw new IllegalArgumentException("value must be 0..1000");
11             total += value;
12         }
13         return total;
14     }
15     public static boolean canPartition(int[] nums) {
16         int sum = total(nums);
17         if ((sum & 1) != 0) return false;
18         int target = sum / 2;
19         boolean[] reachable = new boolean[target + 1];
20         reachable[0] = true;
21         for (int value : nums) {
22             for (int amount = target; amount >= value; amount--) reachable[amount] |= reachable[amount - value];
23         }
24         return reachable[target];
25     }
26     // Baseline: select or omit each physical occurrence. Small inputs only.
27     public static boolean baseline(int[] nums) {
28         int sum = total(nums);
29         return (sum & 1) == 0 && select(nums, 0, sum / 2);
30     }
31     private static boolean select(int[] nums, int index, int remaining) {
32         if (remaining == 0) return true;
33         if (index == nums.length) return false;
34         return select(nums, index + 1, remaining) || nums[index] <= remaining && select(nums, index + 1, remaining - nums[index]);
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate all occurrences and compute the complete total.
The bounded total fits int. For an even total, only sum zero starts reachable. Equal-valued indices remain separate physical occurrences.
input
[1,5,11,5]
phase
"initial"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
previous
null
Begin one physical occurrence layer.
Both transition alternatives must use this old layer. The saved row is explanatory; Java relies on descending order instead of cloning it.
input
[1,5,11,5]
phase
"item-start"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
11
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
11
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
10
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
10
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
9
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
9
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
8
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
8
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
7
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
7
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
6
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
6
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
5
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
5
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
4
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
4
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
3
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
3
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
2
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
2
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,false,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
1
before
false
predecessor
true
next
true
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
amount
1
before
false
predecessor
true
next
true
This occurrence layer is complete.
Every amount now describes subsets of the complete processed prefix, including the current occurrence. No deduplication of equal values is permitted.
input
[1,5,11,5]
phase
"item-complete"
total
22
target
11
reachable
[true,true,false,false,false,false,false,false,false,false,false,false]
index
0
value
1
previous
[true,false,false,false,false,false,false,false,false,false,false,false]
Begin one physical occurrence layer.
Both transition alternatives must use this old layer. The saved row is explanatory; Java relies on descending order instead of cloning it.
input
[1,5,11,5]
phase
"item-start"
total
22
target
11
reachable
[true,true,false,false,false,false,false,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,true,false,false,false,false,false,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
amount
11
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,false,false,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
amount
11
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,true,false,false,false,false,false,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
amount
10
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,false,false,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
amount
10
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,true,false,false,false,false,false,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
amount
9
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,false,false,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
amount
9
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,true,false,false,false,false,false,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
amount
8
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,false,false,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
amount
8
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,true,false,false,false,false,false,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
amount
7
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,false,false,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
amount
7
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,true,false,false,false,false,false,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
amount
6
before
false
predecessor
true
next
true
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,false,true,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
amount
6
before
false
predecessor
true
next
true
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,true,false,false,false,false,true,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
amount
5
before
false
predecessor
true
next
true
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
amount
5
before
false
predecessor
true
next
true
This occurrence layer is complete.
Every amount now describes subsets of the complete processed prefix, including the current occurrence. No deduplication of equal values is permitted.
input
[1,5,11,5]
phase
"item-complete"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,false,false]
index
1
value
5
previous
[true,true,false,false,false,false,false,false,false,false,false,false]
Begin one physical occurrence layer.
Both transition alternatives must use this old layer. The saved row is explanatory; Java relies on descending order instead of cloning it.
input
[1,5,11,5]
phase
"item-start"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,false,false]
index
2
value
11
previous
[true,true,false,false,false,true,true,false,false,false,false,false]
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,false,false]
index
2
value
11
previous
[true,true,false,false,false,true,true,false,false,false,false,false]
amount
11
before
false
predecessor
true
next
true
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,false,true]
index
2
value
11
previous
[true,true,false,false,false,true,true,false,false,false,false,false]
amount
11
before
false
predecessor
true
next
true
This occurrence layer is complete.
Every amount now describes subsets of the complete processed prefix, including the current occurrence. No deduplication of equal values is permitted.
input
[1,5,11,5]
phase
"item-complete"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,false,true]
index
2
value
11
previous
[true,true,false,false,false,true,true,false,false,false,false,false]
Begin one physical occurrence layer.
Both transition alternatives must use this old layer. The saved row is explanatory; Java relies on descending order instead of cloning it.
input
[1,5,11,5]
phase
"item-start"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,false,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,false,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
amount
11
before
true
predecessor
true
next
true
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,false,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
amount
11
before
true
predecessor
true
next
true
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,false,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
amount
10
before
false
predecessor
true
next
true
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,true,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
amount
10
before
false
predecessor
true
next
true
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,true,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
amount
9
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,true,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
amount
9
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,true,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
amount
8
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,true,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
amount
8
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,true,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
amount
7
before
false
predecessor
false
next
false
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,true,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
amount
7
before
false
predecessor
false
next
false
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,true,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
amount
6
before
true
predecessor
true
next
true
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,true,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
amount
6
before
true
predecessor
true
next
true
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[1,5,11,5]
phase
"candidate"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,true,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
amount
5
before
true
predecessor
true
next
true
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[1,5,11,5]
phase
"commit"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,true,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
amount
5
before
true
predecessor
true
next
true
This occurrence layer is complete.
Every amount now describes subsets of the complete processed prefix, including the current occurrence. No deduplication of equal values is permitted.
input
[1,5,11,5]
phase
"item-complete"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,true,true]
index
3
value
5
previous
[true,true,false,false,false,true,true,false,false,false,false,true]
Read half-total reachability and use the complement.
A target subset and its unselected complement have equal totals. Empty groups are allowed, so an empty or all-zero input is true.
input
[1,5,11,5]
phase
"complete"
total
22
target
11
reachable
[true,true,false,false,false,true,true,false,false,false,true,true]
previous
null
Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
result
true

Odd total rejects after validation

Input: [1,2,3,5] · Equal occurrence partition exists: false

Step 1 of 3: Validate all occurrences and compute the complete total.

The bounded total fits int. For an even total, only sum zero starts reachable. Equal-valued indices remain separate physical occurrences.

Equal partition — one-use occurrences and descending sums

Phase: initial.

Original occurrences: [1,2,3,5]. Total=11. The total is odd, so no half-integer target table is allocated.

State after this step
Variable	Value
input	`[1,2,3,5]`
phase	`"initial"`
total	`11`
target	`null`
reachable	`[]`
previous	`null`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static int total(int[] nums) {
 6         Objects.requireNonNull(nums, "nums");
 7         if (nums.length > 200) throw new IllegalArgumentException("too many occurrences");
 8         int total = 0;
 9         for (int value : nums) {
10             if (value < 0 || value > 1_000) throw new IllegalArgumentException("value must be 0..1000");
11             total += value;
12         }
13         return total;
14     }
15     public static boolean canPartition(int[] nums) {
16         int sum = total(nums);
17         if ((sum & 1) != 0) return false;
18         int target = sum / 2;
19         boolean[] reachable = new boolean[target + 1];
20         reachable[0] = true;
21         for (int value : nums) {
22             for (int amount = target; amount >= value; amount--) reachable[amount] |= reachable[amount - value];
23         }
24         return reachable[target];
25     }
26     // Baseline: select or omit each physical occurrence. Small inputs only.
27     public static boolean baseline(int[] nums) {
28         int sum = total(nums);
29         return (sum & 1) == 0 && select(nums, 0, sum / 2);
30     }
31     private static boolean select(int[] nums, int index, int remaining) {
32         if (remaining == 0) return true;
33         if (index == nums.length) return false;
34         return select(nums, index + 1, remaining) || nums[index] <= remaining && select(nums, index + 1, remaining - nums[index]);
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate all occurrences and compute the complete total.
The bounded total fits int. For an even total, only sum zero starts reachable. Equal-valued indices remain separate physical occurrences.
input
[1,2,3,5]
phase
"initial"
total
11
target
null
reachable
[]
previous
null
An odd total cannot split into equal integer sums.
All values have already been validated. No target table is allocated for this early result.
input
[1,2,3,5]
phase
"odd"
total
11
target
null
reachable
[]
previous
null
Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
result
false

Empty and zero target

Input: [] · Equal occurrence partition exists: true

Step 1 of 3: Validate all occurrences and compute the complete total.

The bounded total fits int. For an even total, only sum zero starts reachable. Equal-valued indices remain separate physical occurrences.

Equal partition — one-use occurrences and descending sums

Phase: initial.

Original occurrences: []. Total=0. Target=0; a target subset and its complement have equal sums.

Live exact-sum reachability

0: trueexact-sum state

State after this step
Variable	Value
input	`[]`
phase	`"initial"`
total	`0`
target	`0`
reachable	`[true]`
previous	`null`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static int total(int[] nums) {
 6         Objects.requireNonNull(nums, "nums");
 7         if (nums.length > 200) throw new IllegalArgumentException("too many occurrences");
 8         int total = 0;
 9         for (int value : nums) {
10             if (value < 0 || value > 1_000) throw new IllegalArgumentException("value must be 0..1000");
11             total += value;
12         }
13         return total;
14     }
15     public static boolean canPartition(int[] nums) {
16         int sum = total(nums);
17         if ((sum & 1) != 0) return false;
18         int target = sum / 2;
19         boolean[] reachable = new boolean[target + 1];
20         reachable[0] = true;
21         for (int value : nums) {
22             for (int amount = target; amount >= value; amount--) reachable[amount] |= reachable[amount - value];
23         }
24         return reachable[target];
25     }
26     // Baseline: select or omit each physical occurrence. Small inputs only.
27     public static boolean baseline(int[] nums) {
28         int sum = total(nums);
29         return (sum & 1) == 0 && select(nums, 0, sum / 2);
30     }
31     private static boolean select(int[] nums, int index, int remaining) {
32         if (remaining == 0) return true;
33         if (index == nums.length) return false;
34         return select(nums, index + 1, remaining) || nums[index] <= remaining && select(nums, index + 1, remaining - nums[index]);
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate all occurrences and compute the complete total.
The bounded total fits int. For an even total, only sum zero starts reachable. Equal-valued indices remain separate physical occurrences.
input
[]
phase
"initial"
total
0
target
0
reachable
[true]
previous
null
Read half-total reachability and use the complement.
A target subset and its unselected complement have equal totals. Empty groups are allowed, so an empty or all-zero input is true.
input
[]
phase
"complete"
total
0
target
0
reachable
[true]
previous
null
Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
result
true

Zero occurrences add no new sums

Input: [0,0] · Equal occurrence partition exists: true

Step 1 of 11: Validate all occurrences and compute the complete total.

The bounded total fits int. For an even total, only sum zero starts reachable. Equal-valued indices remain separate physical occurrences.

Equal partition — one-use occurrences and descending sums

Phase: initial.

Original occurrences: [0,0]. Total=0. Target=0; a target subset and its complement have equal sums.

Live exact-sum reachability

0: trueexact-sum state

State after this step
Variable	Value
input	`[0,0]`
phase	`"initial"`
total	`0`
target	`0`
reachable	`[true]`
previous	`null`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static int total(int[] nums) {
 6         Objects.requireNonNull(nums, "nums");
 7         if (nums.length > 200) throw new IllegalArgumentException("too many occurrences");
 8         int total = 0;
 9         for (int value : nums) {
10             if (value < 0 || value > 1_000) throw new IllegalArgumentException("value must be 0..1000");
11             total += value;
12         }
13         return total;
14     }
15     public static boolean canPartition(int[] nums) {
16         int sum = total(nums);
17         if ((sum & 1) != 0) return false;
18         int target = sum / 2;
19         boolean[] reachable = new boolean[target + 1];
20         reachable[0] = true;
21         for (int value : nums) {
22             for (int amount = target; amount >= value; amount--) reachable[amount] |= reachable[amount - value];
23         }
24         return reachable[target];
25     }
26     // Baseline: select or omit each physical occurrence. Small inputs only.
27     public static boolean baseline(int[] nums) {
28         int sum = total(nums);
29         return (sum & 1) == 0 && select(nums, 0, sum / 2);
30     }
31     private static boolean select(int[] nums, int index, int remaining) {
32         if (remaining == 0) return true;
33         if (index == nums.length) return false;
34         return select(nums, index + 1, remaining) || nums[index] <= remaining && select(nums, index + 1, remaining - nums[index]);
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate all occurrences and compute the complete total.
The bounded total fits int. For an even total, only sum zero starts reachable. Equal-valued indices remain separate physical occurrences.
input
[0,0]
phase
"initial"
total
0
target
0
reachable
[true]
previous
null
Begin one physical occurrence layer.
Both transition alternatives must use this old layer. The saved row is explanatory; Java relies on descending order instead of cloning it.
input
[0,0]
phase
"item-start"
total
0
target
0
reachable
[true]
index
0
value
0
previous
[true]
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[0,0]
phase
"candidate"
total
0
target
0
reachable
[true]
index
0
value
0
previous
[true]
amount
0
before
true
predecessor
true
next
true
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[0,0]
phase
"commit"
total
0
target
0
reachable
[true]
index
0
value
0
previous
[true]
amount
0
before
true
predecessor
true
next
true
This occurrence layer is complete.
Every amount now describes subsets of the complete processed prefix, including the current occurrence. No deduplication of equal values is permitted.
input
[0,0]
phase
"item-complete"
total
0
target
0
reachable
[true]
index
0
value
0
previous
[true]
Begin one physical occurrence layer.
Both transition alternatives must use this old layer. The saved row is explanatory; Java relies on descending order instead of cloning it.
input
[0,0]
phase
"item-start"
total
0
target
0
reachable
[true]
index
1
value
0
previous
[true]
Read the old target and not-yet-updated smaller predecessor.
Higher amounts have been updated, but this amount and its smaller predecessor still belong to the old occurrence layer. For value zero the self-OR changes nothing.
input
[0,0]
phase
"candidate"
total
0
target
0
reachable
[true]
index
1
value
0
previous
[true]
amount
0
before
true
predecessor
true
next
true
Commit this exact-sum existence result.
The occurrence is used at most once. Reversing the scan would allow this same index to feed later updates repeatedly.
input
[0,0]
phase
"commit"
total
0
target
0
reachable
[true]
index
1
value
0
previous
[true]
amount
0
before
true
predecessor
true
next
true
This occurrence layer is complete.
Every amount now describes subsets of the complete processed prefix, including the current occurrence. No deduplication of equal values is permitted.
input
[0,0]
phase
"item-complete"
total
0
target
0
reachable
[true]
index
1
value
0
previous
[true]
Read half-total reachability and use the complement.
A target subset and its unselected complement have equal totals. Empty groups are allowed, so an empty or all-zero input is true.
input
[0,0]
phase
"complete"
total
0
target
0
reachable
[true]
previous
null
Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
result
true

Test the contract

Input: nums=[0,0,0]
Output: true
Zero target with empty groups allowed.
Input: nums=[1,1]
Output: true
Equal-valued physical occurrences are separate.
Input: nums=[2,2,3,5]
Output: false
Even total does not imply a target subset exists.
Input: nums=[1000,1000]
Output: true
Largest allowed values can split.
Input: nums=[-1]
Output: IllegalArgumentException
Negative input is outside the enforced domain.
Input: nums=null
Output: NullPointerException
Null is not empty.

Common mistakes and counterexamples

Use an ascending amount loop

Counterexample: [1,2,5] can falsely reach four by repeatedly using the single 1.

Scan downward so every read belongs to the previous occurrence layer.

Deduplicate equal values

Counterexample: [1,1] is partitionable using one occurrence on each side; removing a copy changes the total and supply.

Keep index occurrences distinct.

Require nonempty subsets without stating it

Counterexample: The documented empty array and [0] are true here.

Use the explicit empty-subset convention, or redesign the state for a different requirement.

Return on odd parity before validating all values

Counterexample: A late negative or oversized value is invalid even when a partial sum looks odd.

Validate and compute the complete bounded total first.

Follow-ups

Return both index subsets.

Record the occurrence that first makes each positive sum reachable and its predecessor sum, taking care not to overwrite ownership or reuse an index. Backtrack a target witness and form its complement. Zeros and T=0 need an explicit policy; a full occurrence table gives a simpler reconstruction proof.

Find the minimum difference instead of equality.

Compute reachable sums up to floor(S/2) and choose the largest reachable s. The other side totals S−s, so the difference is S−2s. An odd total is no longer an immediate rejection.

Allow negative values.

The bounded nonnegative target array and amount scan direction no longer apply directly. Use a range-offset table spanning possible signed sums or sets of reachable sums from a frozen old layer. Recheck total bounds, complexity, and ownership; a zero/positive-only descending loop cannot be reused unchanged.

Related foundations

Dynamic programming: state before recurrence

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Familiar interview problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.