Published by Dimitris Kougioumtzis · Updated
Find a subset whose sum is half the total; every item is used at most once.
Reject odd totals, then ask whether a subset reaches half of an even total.
When to use Equal-sum partition
Splitting nonnegative weights into equal sums.
Choosing an alternative
Subset sum permits an arbitrary target rather than deriving half the total.
Worked example: input and state changes
Example input
1,5,11,5
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], "active": [] }Step 7: Try item 1 at subtotal 6.
State at this checkpoint
{ "values": [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], "active": [ 6 ] }Step 14: Try item 5 at subtotal 10.
State at this checkpoint
{ "values": [ 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], "active": [ 10 ] }Step 21: Try item 5 at subtotal 11.
State at this checkpoint
{ "values": [ 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1 ], "active": [ 11 ] }Step 28: Equal partition is possible; half-total 11.
State at this checkpoint
{ "values": [ 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1 ], "active": [ 11 ] }
Expected final state
Equal partition is possible; half-total 11.
Complexity and input bounds
Family: Dynamic programming. Time complexity: O(items × sum).
Space complexity: O(total sum) reachability storage.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
1–16 integers between 0 and 30.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Equal sum does not require equal item counts; each item is still used at most once.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 | // 1–16 nonnegative values <= 30. Returns 1 if two subsets have equal sum, else 0; empty subsets are allowed. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(a, n) { let sum = 0; for (let i = 0; i < n; i++) { sum += a[i]; } if (sum % 2 != 0) { return 0; } let target = sum >> 1; let dp = Array(256).fill(0); dp[0] = 1; for (let i = 0; i < n; i++) { for (let s = target; s >= a[i]; s--) { if (dp[s - a[i]] == 1) { dp[s] = 1; } } } return dp[target]; } |
Source
Foundational dynamic-programming paper. It establishes the general method, not the first publication or exact recurrence of this particular teaching example.
- The theory of dynamic programming
Richard Bellman (1954). Foundational method paper.