AFTD Auto-Formalizing Theoretical Domains

SubsetSumToPartition.Partition

defimported Lean

Given a weight function $v : U \to \mathbb{N}$ on a finite type $U$, the predicate asserts that some subset $S \subseteq U$ has the same total weight as its complement, i.e.\ $\exists S,\ \sum_{b \in S} v(b) = \sum_{b \in S^{c}} v(b)$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {U : Type*} [Fintype U] [DecidableEq U] in
noncomputable def SubsetSumToPartition.Partition (v : U → ℕ) : Prop
Defined in
TCSlib, `SubsetSumToPartition.Partition`
Lean proof
By Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
none listed
Used by 3

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {U : Type*} [Fintype U] [DecidableEq U] in
/-- The Partition problem: Given a finite set `U` and a weight function `v`, does there exist a subset `S` whose sum equals the sum of its complement `Sᶜ`? -/
noncomputable def SubsetSumToPartition.Partition (v : U → ℕ) : Prop :=
  ∃ S : Finset U, (∑ b ∈ S, v b) = (∑ b ∈ Sᶜ, v b)
See it in the graphDiscuss this resultChallenge it