Skip to content

Partition problem

The problem of dividing a multiset of positive integers into two exhaustive parts with equal sums, or minimizing their sum difference.

Version
v1 · 2026-09-28 · History
Domain-specific #
11217
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomains
Computational Complexity, NP Complete Problems → Computer Science & Software Engineering
Aliases
Number partitioning

Core Idea

The partition problem assigns every occurrence in a multiset of positive integers to one of two sides and asks whether the sums can be equal. Equality is possible only if one side totals half the overall sum. The optimization version always seeks a split, choosing one whose absolute sum difference is minimal.

The problem is NP-complete in its decision form but weakly so: dynamic programming can run in time polynomial in the numeric total, which is pseudo-polynomial relative to binary input length. This explains why many practical instances are manageable. Partition is a half-total subset-sum case and a two-bin number-partitioning case, but should not be conflated with strongly hard 3-partition.

Structural Signature

Sig role-phrases:

  • positive-integer multiset — supplies weighted items with multiplicity It is essential. Counterfactual: Removing weights or multiplicity changes the instance class.
  • two submultisets — receive every item exactly once It is essential. Counterfactual: Omitted or duplicated items do not form a partition.
  • subset sums — aggregate item weights within each side It is essential. Counterfactual: Another aggregation criterion defines a different balancing problem.
  • equality target — sets the yes/no requirement at half the total It is essential. Counterfactual: Allowing arbitrary imbalance changes decision to approximation or optimization.
  • difference objective — quantifies best possible imbalance in the optimization form It is characteristic. Counterfactual: A feasible/no-feasible answer does not provide optimization value.
  • binary magnitude encoding — explains why pseudo-polynomial time does not contradict NP-completeness It is essential. Counterfactual: Treating numeric value as input length misstates complexity.

What It Is Not

  • It is not arbitrary set partition without numeric weights.
  • It is not subset sum with any externally chosen target.
  • It is not 3-partition.
  • It is not multiway partitioning with unrestricted k.
  • Closest near-miss. Two-way number partitioning is the same core problem, whereas 3-partition has variable many triples and different strong-hardness behavior.

Scope of Application

  • Complexity theory. The problem illustrates weak NP-completeness.
  • Dynamic programming. Reachable subset sums yield pseudo-polynomial solutions.
  • Scheduling and load balance. Two-machine assignments resemble minimum-difference partitioning.
  • Approximation algorithms. Heuristics trade guarantees and speed for large instances.

Clarity

Specify multiset semantics, positivity, decision versus optimization version, integer encoding, item count, total sum, exact or approximate requirement, and tie handling. A claim of polynomial runtime must say whether it is polynomial in input bits or numeric total.

Manages Complexity

A simple equal-sum condition hides an exponential choice space. Additivity permits compact dynamic programming over totals, while large binary-encoded magnitudes restore worst-case difficulty. Complexity depends on representation as much as on the apparent number of items.

Abstract Reasoning

  1. Compute the total and reject exact equality immediately if it is odd.
  2. Set the target to half the total.
  3. Represent reachable subset sums by dynamic programming or another exact method.
  4. Recover a target subset and place all remaining occurrences on the other side.
  5. For optimization, locate the reachable sum nearest half the total.
  6. Verify exhaustive disjoint assignment and compute imbalance.
  7. Report optimality or approximation guarantee and resource dependence.

Knowledge Transfer

The balancing form transfers to two-way scheduling and load distribution when costs add and every item is assigned once. It stops at multiple bins, vector costs, precedence, or splittable jobs without modifying the model. The cargo is exhaustive two-way additive balance.

Examples

Applied / In Practice

The multiset {3,1,1,2,2,1} splits into {1,1,1,2} and {2,3}, each summing to five.

Mapped back: coverage → Every occurrence is assigned once.; equality → Both totals match..

Applied / In Practice

The multiset {2,5} has odd total seven and therefore cannot have two equal integer sums.

Mapped back: parity certificate → An odd total rules out half-sum equality..

Applied / In Practice

Find a subset totaling six in a multiset whose overall total is twenty.

Mapped back: boundary → The target is not half the total, so this is subset sum..

Structural Tensions

T1 — Worst-Case Hardness versus Practical Tractability. NP-completeness coexists with effective heuristics and pseudo-polynomial algorithms for moderate totals.

Diagnostic: Report item count, magnitude, distribution, and optimality guarantee rather than calling every instance hard.

T2 — Exact Equality versus Minimum Imbalance. The decision version fails on many instances where optimization still returns a useful near balance.

Diagnostic: State whether output is feasibility, optimal difference, or approximation ratio.

Structural–Framed Character

The feasibility relation is structural; the practical difficulty is framed by number encoding and instance distribution. NP-completeness is not a prediction that a particular instance resists solution.

Structural Core vs. Domain Accent

The skeleton is binary allocation under equal aggregate load. Number theory and algorithms supply integers, subset sums, NP-completeness, and pseudo-polynomial dynamic programming. These commitments distinguish it from generic grouping.

  • Approved root. Frozen DAG placement is unparented.

  • Related — subset sum and multiway number partitioning. Partition is a special case of each under precise parameter choices.

Relationships to Other Abstractions

Local relationship map for Partition problemParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Partition problemDOMAINDomain-specific abstraction: Matroid-Constrained Number Partitioning — is a kind ofMatroid-Constra…DOMAIN

Current abstraction Partition problem Domain-specific

Foundational — no parent edges in the catalog.

Children (1) — more specific cases that build on this

  • Matroid-Constrained Number Partitioning Domain-specific is a kind of Partition problem

    Matroid-Constrained Number Partitioning is a strict kind of Partition problem: it partitions numbers among subsets while adding matroid-independence constraints.

Neighborhood in Abstraction Space

Partition problem sits in a crowded region of the domain-specific corpus (26th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Combinatorial Optimization & Game Problems (12 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With

  • Set partition. Tell: Divides a set without necessarily balancing numeric sums.
  • Subset sum. Tell: Uses an arbitrary target and need not emphasize the complementary side.
  • 3-partition. Tell: Forms many three-item equal-sum groups and is strongly NP-complete.
  • Knapsack. Tell: Optimizes value under capacity rather than equal use of all items.

References

  • Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Partition_problem (revision 1361574558).
  • Preserved source candidate: http://bit-player.org/extras/bph-publications/AmSci-2002-03-Hayes-NPP.pdf
  • Preserved source candidate: https://books.google.com/books?id=4YD6AxV95zEC&pg=PA125
  • Preserved source candidate: https://ijcai.org/papers09/Papers/IJCAI09-096.pdf
  • Preserved source candidate: https://archive.org/details/computersintract0000gare
  • Preserved source candidate: https://archive.org/details/computersintract0000gare/page/96
  • Preserved source candidate: https://www.ics.uci.edu/~goodrich/teach/cs162/notes/pnp3.pdf
  • Preserved source candidate: https://books.google.com/books?id=u5DB7gck08YC&pg=PA97
  • Preserved source candidate: https://archive.org/details/knapsackproblems0000mart/page/105

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.