import Mathlib /-! # 3Sum Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. ## Constraints - 3 <= nums.length <= 3000 - -10^5 <= nums[i] <= 10^5 ## Provided examples - `nums = [-1, 0, 1, 2, -1, -4]` → `[[-1, -1, 2], [-1, 0, 1]]` - `nums = [0, 1, 1]` → `[]` - `nums = [0, 0, 0]` → `[[0, 0, 0]]` ## Synthesized negative examples - invalid input: `nums = [-100001, 0, 0]` ([structural] a predicate that admits -10^5 <= nums[i] <= 10^5. one below the stated minimum element value) - invalid input: `nums = []` ([structural] a predicate that admits 3 <= nums.length <= 3000. empty where at least three elements are required) - invalid input: `nums = [100001, 0, 0]` ([structural] a predicate that admits -10^5 <= nums[i] <= 10^5. one above the stated maximum element value) - `nums = [-1, 0, 1, 2, -1, -4]` → `[[-1, -1, 2], [-1, -1, 2], [-1, 0, 1]]` is wrong ([structural] solution set may contain duplicate triplets. duplicate of a valid triple) - `nums = [0, 1, 1]` → `[[0, 0, 0]]` is wrong ([structural] distinct index condition omitted. repeats the single zero three times) - `nums = [0, 0, 0]` → `[[0, 0, 0], [0, 0, 0]]` is wrong ([structural] solution set is not required to be duplicate-free. true triplet appears twice and is otherwise valid) -/ namespace P3sum abbrev Input := List Int abbrev Output := List (List Int) /-! ### Specification helpers -/ /-- `t` is the nondecreasing arrangement of values at three pairwise distinct indices of `nums` and sums to zero. -/ def IsZeroSumTriplet (nums : List Int) (t : List Int) : Prop := t.length = 3 ∧ t.Pairwise (· ≤ ·) ∧ t.sum = 0 ∧ ∃ i j k : ℕ, i < nums.length ∧ j < nums.length ∧ k < nums.length ∧ i ≠ j ∧ i ≠ k ∧ j ≠ k ∧ List.Perm t [nums[i]!, nums[j]!, nums[k]!] /-! ### Validity predicate (V) -/ /-- Valid input: 3 to 3000 elements, each between -10^5 and 10^5 inclusive. -/ def isValidInput (input : Input) : Bool := 3 ≤ input.length && input.length ≤ 3000 && input.all (fun x => -100000 ≤ x && x ≤ 100000) /-! ### Ideal specification (P_spec) -/ /-- `result` enumerates without repetition some finite set `S` of zero-sum triples, and `S` contains every zero-sum triple. -/ def threeSum_spec (input : Input) (result : Output) : Prop := ∃ S : Finset (List Int), ((∀ t ∈ S, IsZeroSumTriplet input t) ∧ result.Nodup ∧ ∀ t, t ∈ result ↔ t ∈ S) ∧ ∀ t, IsZeroSumTriplet input t → t ∈ S /-! ### Decidable specification (P_check) -/ /-- Decidable form of `IsZeroSumTriplet`: same clauses, with the index triple bounded to `Fin nums.length`. -/ def isZeroSumTripletBool (nums : List Int) (t : List Int) : Bool := decide (t.length = 3 ∧ t.Pairwise (· ≤ ·) ∧ t.sum = 0 ∧ ∃ i j k : Fin nums.length, i ≠ j ∧ i ≠ k ∧ j ≠ k ∧ List.Perm t [nums[i], nums[j], nums[k]]) /-- Every ordered triple of values drawn from `nums`; contains every list that could satisfy `IsZeroSumTriplet`. -/ def candidateTriplets (nums : List Int) : List (List Int) := nums.flatMap fun a => nums.flatMap fun b => nums.map fun c => [a, b, c] /-- Executable checker for `threeSum_spec`, with `S` realized as `result.toFinset` and completeness checked over the candidates. -/ def threeSum_check (input : Input) (result : Output) : Bool := decide (result.Nodup ∧ (∀ t ∈ result, isZeroSumTripletBool input t = true) ∧ (∀ t ∈ candidateTriplets input, isZeroSumTripletBool input t = true → t ∈ result)) theorem root_of_bridges (reflect : ∀ nums t, isZeroSumTripletBool nums t = true ↔ IsZeroSumTriplet nums t) (enumerate : ∀ nums t, IsZeroSumTriplet nums t → t ∈ candidateTriplets nums) (input : Input) (result : Output) : threeSum_check input result ↔ threeSum_spec input result := by classical simp only [threeSum_check, decide_eq_true_eq, reflect] constructor · rintro ⟨hn, hs, hc⟩ refine ⟨result.toFinset, ⟨?_, hn, ?_⟩, ?_⟩ · simpa using hs · simp · intro t ht exact List.mem_toFinset.mpr (hc t (enumerate input t ht) ht) · rintro ⟨S, ⟨hs, hn, hm⟩, hc⟩ exact ⟨hn, fun t ht => hs t ((hm t).mp ht), fun t _ ht => (hm t).mpr (hc t ht)⟩ theorem triplet_reflect (nums t : List Int) : isZeroSumTripletBool nums t = true ↔ IsZeroSumTriplet nums t := by simp only [isZeroSumTripletBool, decide_eq_true_eq, IsZeroSumTriplet] constructor · rintro ⟨hl, ho, hs, i, j, k, hij, hik, hjk, hp⟩ refine ⟨hl, ho, hs, i.val, j.val, k.val, i.isLt, j.isLt, k.isLt, fun e => hij (Fin.ext e), fun e => hik (Fin.ext e), fun e => hjk (Fin.ext e), ?_⟩ simpa only [Fin.getElem_fin, getElem!_pos nums i.val i.isLt, getElem!_pos nums j.val j.isLt, getElem!_pos nums k.val k.isLt] using hp · rintro ⟨hl, ho, hs, i, j, k, hi, hj, hk, hij, hik, hjk, hp⟩ refine ⟨hl, ho, hs, ⟨i, hi⟩, ⟨j, hj⟩, ⟨k, hk⟩, ?_, ?_, ?_, ?_⟩ · intro e exact hij (congrArg Fin.val e) · intro e exact hik (congrArg Fin.val e) · intro e exact hjk (congrArg Fin.val e) · simpa only [Fin.getElem_fin, getElem!_pos nums i hi, getElem!_pos nums j hj, getElem!_pos nums k hk] using hp theorem triplet_enumerate (nums t : List Int) (ht : IsZeroSumTriplet nums t) : t ∈ candidateTriplets nums := by rcases ht with ⟨hl, _, _, i, j, k, hi, hj, hk, _, _, _, hp⟩ rcases List.length_eq_three.mp hl with ⟨a, b, c, rfl⟩ have hm : ∀ x ∈ [a, b, c], x ∈ nums := by intro x hx have hx' := hp.mem_iff.mp hx simp only [List.mem_cons, List.not_mem_nil, or_false] at hx' rcases hx' with rfl | rfl | rfl · simpa only [getElem!_pos nums i hi] using (List.getElem_mem hi) · simpa only [getElem!_pos nums j hj] using (List.getElem_mem hj) · simpa only [getElem!_pos nums k hk] using (List.getElem_mem hk) simp only [candidateTriplets, List.mem_flatMap, List.mem_map] exact ⟨a, hm a (by simp), b, hm b (by simp), c, hm c (by simp), rfl⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem threeSum_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : threeSum_check input result ↔ threeSum_spec input result := by exact root_of_bridges triplet_reflect triplet_enumerate input result /-! ### Implementation helpers -/ /-- The input as an array sorted ascending, so equal values become adjacent. -/ def sortNums (nums : List Int) : Array Int := Array.qsort nums.toArray (fun x y => decide (x ≤ y)) /-- Two-pointer scan of the sorted span `[l, r]` listing each value-distinct pair summing to `target`, in discovery order. -/ def twoSumPairs (a : Array Int) (lo l r : Nat) (target : Int) : List (List Int) := if h : l < r then if lo < l ∧ a[l]! == a[l - 1]! then twoSumPairs a lo (l + 1) r target else let x := a[l]! let y := a[r]! let s := x + y if s < target then twoSumPairs a lo (l + 1) r target else if target < s then twoSumPairs a lo l (r - 1) target else [x, y] :: twoSumPairs a lo (l + 1) r target else [] termination_by r - l decreasing_by all_goals omega /-- Scan each index of the sorted array as the smallest triplet value, accumulating triplets in reverse discovery order. -/ def outerLoop (a : Array Int) (i : Nat) (acc : List (List Int)) : List (List Int) := if h : i + 2 < a.size then if 0 < i ∧ a[i]! == a[i - 1]! then outerLoop a (i + 1) acc else let pairs := twoSumPairs a (i + 1) (i + 1) (a.size - 1) (-a[i]!) outerLoop a (i + 1) ((pairs.map (a[i]! :: ·)).reverse ++ acc) else acc termination_by a.size - i decreasing_by all_goals omega /-! ### Main algorithm (impl) -/ /-- Sort the input, then fix each distinct value in turn and find complementary pairs with a two-pointer scan, skipping duplicates. -/ def zeroSumTriplets (nums : List Int) : List (List Int) := (outerLoop (sortNums nums) 0 []).reverse /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem zeroSumTriplets_correct (input : Input) (h : isValidInput input) : threeSum_spec input (zeroSumTriplets input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [-1, 0, 1, 2, -1, -4] #guard isValidInput [0, 1, 1] #guard isValidInput [0, 0, 0] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput [-100001, 0, 0]) #guard !(isValidInput []) #guard !(isValidInput [100001, 0, 0]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard threeSum_check [(-1), 0, 1, 2, (-1), (-4)] [[(-1), (-1), 2], [(-1), 0, 1]] #guard threeSum_check [0, 1, 1] [] #guard threeSum_check [0, 0, 0] [[0, 0, 0]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(threeSum_check [(-1), 0, 1, 2, (-1), (-4)] [[(-1), (-1), 2], [(-1), (-1), 2], [(-1), 0, 1]]) #guard !(threeSum_check [0, 1, 1] [[0, 0, 0]]) #guard !(threeSum_check [0, 0, 0] [[0, 0, 0], [0, 0, 0]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard zeroSumTriplets [(-1), 0, 1, 2, (-1), (-4)] == [[(-1), (-1), 2], [(-1), 0, 1]] #guard zeroSumTriplets [0, 1, 1] == [] #guard zeroSumTriplets [0, 0, 0] == [[0, 0, 0]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard threeSum_check [(-1), 0, 1, 2, (-1), (-4)] (zeroSumTriplets [(-1), 0, 1, 2, (-1), (-4)]) #guard threeSum_check [0, 1, 1] (zeroSumTriplets [0, 1, 1]) #guard threeSum_check [0, 0, 0] (zeroSumTriplets [0, 0, 0]) end P3sum