AFTD Auto-Formalizing Theoretical Domains

SubsetSumToPartition.SubsetSum

defimported Lean

Given a weight function $w : U \to \mathbb{N}$ on a finite type $U$ and a target $T \in \mathbb{N}$, the predicate asserts that some subset $S \subseteq U$ has total weight exactly $T$, i.e.\ $\exists S,\ \sum_{a \in S} w(a) = T$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {U : Type*} [Fintype U] [DecidableEq U] in
noncomputable def SubsetSumToPartition.SubsetSum (w : U → ℕ) (T : ℕ) : Prop
Defined in
TCSlib, `SubsetSumToPartition.SubsetSum`
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 Subset Sum problem: Given a weight function `w` and a target `T`, does there exist a subset `S` of `U` whose weights sum exactly to `T`? -/
noncomputable def SubsetSumToPartition.SubsetSum (w : U → ℕ) (T : ℕ) : Prop :=
  ∃ S : Finset U, (∑ a ∈ S, w a) = T
See it in the graphDiscuss this resultChallenge it