import Mathlib /-! # Combination Sum Ii Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination. Note: The solution set must not contain duplicate combinations. ## Constraints - 1 <= candidates.length <= 100 - 1 <= candidates[i] <= 50 - 1 <= target <= 30 ## Provided examples - `candidates = [10, 1, 2, 7, 6, 1, 5], target = 8` → `[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]` - `candidates = [2, 5, 2, 1, 2], target = 5` → `[[1, 2, 2], [5]]` - `candidates = [1, 2], target = 4` → `[]` ## Synthesized negative examples - invalid input: `candidates = [], target = 1` ([structural] a predicate that admits 1 <= candidates.length <= 100. empty list below the one-element minimum) - invalid input: `candidates = [0], target = 1` ([structural] a predicate that admits 1 <= candidates[i] <= 50. one below the element minimum) - invalid input: `candidates = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], target = 1` ([structural] a predicate that admits 1 <= candidates.length <= 100. one past the maximum length) - `candidates = [10, 1, 2, 7, 6, 1, 5], target = 8` → `[[1, 1, 6], [1, 2, 5]]` is wrong ([structural] completeness stated as existence of a valid subset. valid combinations but misses [1,7] and [2,6]) - `candidates = [2, 5, 2, 1, 2], target = 5` → `[[1, 2, 2], [5], [1, 2, 2]]` is wrong ([structural] solution set is not required to be duplicate-free. one combination repeated) - `candidates = [1, 2], target = 4` → `[[1, 2]]` is wrong ([structural] sum required to be target minus one. combination sums to 3, one less than target 4) -/ namespace PCombinationSumIi abbrev Input := (List Nat) × (Nat) abbrev Output := List (List Nat) /-! ### Specification helpers -/ /-- `comb` is a valid combination for `candidates` and `target`: a permutation of a sublist of `candidates` whose entries sum to `target`. -/ def IsValidCombination (candidates : List Nat) (target : Nat) (comb : List Nat) : Prop := (∃ s : List Nat, s.Sublist candidates ∧ s.Perm comb) ∧ comb.sum = target /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 100 candidates, each between 1 and 50, and a target between 1 and 30. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 100 && input.1.all (fun x => 1 ≤ x && x ≤ 50) && 1 ≤ input.2 && input.2 ≤ 30 /-! ### Ideal specification (P_spec) -/ /-- `result` lists exactly the valid combinations of `input`: every entry is valid, no two entries are permutations of one another, and every valid combination is a permutation of some entry. -/ def combinationSum2_spec (input : Input) (result : Output) : Prop := (∀ comb ∈ result, IsValidCombination input.1 input.2 comb) ∧ result.Pairwise (fun a b => ¬ a.Perm b) ∧ ∀ comb : List Nat, IsValidCombination input.1 input.2 comb → ∃ entry ∈ result, entry.Perm comb /-! ### Decidable specification (P_check) -/ /-- Nondecreasing combinations with exact remaining sum, using each value at most as often as `candidates` contains it. -/ def boundedCombos (candidates : List Nat) : Nat → Nat → Nat → List (List Nat) | 0, _, _ => [] | fuel + 1, lo, remaining => if remaining == 0 then [[]] else if remaining < lo then [] else let cap := Nat.min (candidates.count lo) (remaining / lo) (List.range (cap + 1)).flatMap fun copies => (boundedCombos candidates fuel (lo + 1) (remaining - copies * lo)).map fun tail => List.replicate copies lo ++ tail /-- All canonical valid combinations for `candidates` and `target`. -/ def allCanonicalCombos (candidates : List Nat) (target : Nat) : List (List Nat) := boundedCombos candidates (target + 1) 1 target /-- Whether `left` and `right` have the same value counts. -/ def sameMultiset (left right : List Nat) : Bool := (left ++ right).all fun x => decide (left.count x = right.count x) /-- Whether `entry` is a valid combination for `candidates` and `target`. -/ def validEntry (candidates : List Nat) (target : Nat) (entry : List Nat) : Bool := entry.sum == target && entry.all fun x => decide (entry.count x ≤ candidates.count x) /-- Whether no two entries of `result` are permutations of one another. -/ def noPermDuplicate : List (List Nat) → Bool | [] => true | entry :: rest => !(rest.any fun other => sameMultiset entry other) && noPermDuplicate rest /-- Executable checker for `combinationSum2_spec` over canonical value-count combinations. -/ def combinationSum2_check (input : Input) (result : Output) : Bool := result.all (validEntry input.1 input.2) && noPermDuplicate result && (allCanonicalCombos input.1 input.2).all fun canonical => result.any fun entry => sameMultiset entry canonical theorem root_of_bridges (reflection : ∀ (input : Input) (result : Output), combinationSum2_check input result ↔ (∀ comb ∈ result, IsValidCombination input.1 input.2 comb) ∧ result.Pairwise (fun a b => ¬ a.Perm b) ∧ ∀ c ∈ allCanonicalCombos input.1 input.2, ∃ e ∈ result, e.Perm c) (enumeration : ∀ (input : Input), isValidInput input → ∀ comb, IsValidCombination input.1 input.2 comb ↔ ∃ c ∈ allCanonicalCombos input.1 input.2, c.Perm comb) (input : Input) (result : Output) (h : isValidInput input) : combinationSum2_check input result ↔ combinationSum2_spec input result := by rw [reflection] unfold combinationSum2_spec constructor · rintro ⟨hv, hn, hc⟩ refine ⟨hv, hn, ?_⟩ intro comb hb obtain ⟨c, hmem, hp⟩ := (enumeration input h comb).mp hb obtain ⟨e, he, hep⟩ := hc c hmem exact ⟨e, he, hep.trans hp⟩ · rintro ⟨hv, hn, hc⟩ refine ⟨hv, hn, ?_⟩ intro c hm exact hc c ((enumeration input h c).mpr ⟨c, hm, List.Perm.refl _⟩) lemma sublist_perm_iff_count (candidates comb : List Nat) : (∃ s : List Nat, s.Sublist candidates ∧ s.Perm comb) ↔ ∀ x, comb.count x ≤ candidates.count x := by rw [← List.subperm_iff_count] constructor · rintro ⟨s, hs, hp⟩ exact ⟨s, hp, hs⟩ · rintro ⟨s, hp, hs⟩ exact ⟨s, hs, hp⟩ lemma count_valid (candidates : List Nat) (target : Nat) (comb : List Nat) : IsValidCombination candidates target comb ↔ comb.sum = target ∧ ∀ x, comb.count x ≤ candidates.count x := by rw [IsValidCombination, sublist_perm_iff_count] exact and_comm lemma sameMultiset_iff_perm (left right : List Nat) : sameMultiset left right ↔ left.Perm right := by rw [List.perm_iff_count] simp only [sameMultiset, List.all_eq_true, decide_eq_true_eq, List.mem_append] constructor · intro h x by_cases hx : x ∈ left ∨ x ∈ right · exact h x hx · push_neg at hx simp [List.count_eq_zero_of_not_mem hx.1, List.count_eq_zero_of_not_mem hx.2] · intro h x _ exact h x lemma validEntry_iff_valid (candidates : List Nat) (target : Nat) (entry : List Nat) : validEntry candidates target entry ↔ IsValidCombination candidates target entry := by rw [count_valid] simp only [validEntry, Bool.and_eq_true, beq_iff_eq, List.all_eq_true, decide_eq_true_eq] refine and_congr_right fun _ => ?_ constructor · intro h x by_cases hx : x ∈ entry · exact h x hx · simp [List.count_eq_zero_of_not_mem hx] · intro h x _ exact h x lemma noPermDuplicate_iff_pairwise (result : List (List Nat)) : noPermDuplicate result ↔ result.Pairwise (fun a b => ¬ a.Perm b) := by induction result with | nil => simp [noPermDuplicate] | cons entry rest ih => simp [noPermDuplicate, ih, sameMultiset_iff_perm] lemma checker_reflection : ∀ (input : Input) (result : Output), combinationSum2_check input result ↔ (∀ comb ∈ result, IsValidCombination input.1 input.2 comb) ∧ result.Pairwise (fun a b => ¬ a.Perm b) ∧ ∀ c ∈ allCanonicalCombos input.1 input.2, ∃ e ∈ result, e.Perm c := by intro input result simp only [combinationSum2_check, Bool.and_eq_true, List.all_eq_true, validEntry_iff_valid, noPermDuplicate_iff_pairwise, List.any_eq_true, sameMultiset_iff_perm] aesop theorem bounded_sound (cand : List Nat) (fuel lo rem : Nat) (c : List Nat) (hl : 0 < lo) (hm : c ∈ boundedCombos cand fuel lo rem) : c.sum = rem ∧ (∀ x, c.count x ≤ cand.count x) ∧ (∀ x ∈ c, lo ≤ x) := by induction fuel generalizing lo rem c with | zero => simp [boundedCombos] at hm | succ fuel ih => by_cases hr : rem = 0 · simp [boundedCombos, hr] at hm subst c simp [hr] · by_cases hrlo : rem < lo · simp [boundedCombos, hr, hrlo] at hm · simp only [boundedCombos, beq_iff_eq, hr, ↓reduceIte, hrlo, List.mem_flatMap, List.mem_range, List.mem_map] at hm obtain ⟨n, hn, t, ht, rfl⟩ := hm obtain ⟨hs, hc, hb⟩ := ih (lo + 1) (rem - n * lo) t (by omega) ht have hnm : n ≤ min (cand.count lo) (rem / lo) := Nat.le_of_lt_succ hn have hn1 : n ≤ cand.count lo := hnm.trans (Nat.min_le_left _ _) have hn2 : n * lo ≤ rem := (Nat.le_div_iff_mul_le hl).mp (hnm.trans (Nat.min_le_right _ _)) refine ⟨?_, ?_, ?_⟩ · simp only [List.sum_append, List.sum_replicate_nat, hs] omega · intro x by_cases hx : x = lo · subst x have hz : t.count lo = 0 := List.count_eq_zero.mpr (by intro hm have := hb lo hm omega) simp [List.count_append, hz, hn1] · simpa [List.count_append, List.count_replicate, Ne.symm hx] using hc x · intro x hx rcases List.mem_append.mp hx with hx | hx · have := List.eq_of_mem_replicate hx omega · have := hb x hx omega theorem bounded_complete (cand : List Nat) (fuel lo rem : Nat) (c : List Nat) (hf : 0 < fuel) (hl : 0 < lo) (hbound : rem < lo + fuel - 1) (hs : c.sum = rem) (hc : ∀ x, c.count x ≤ cand.count x) (hb : ∀ x ∈ c, lo ≤ x) : ∃ e ∈ boundedCombos cand fuel lo rem, e.Perm c := by induction fuel generalizing lo rem c with | zero => omega | succ fuel ih => by_cases hr : rem = 0 · have he : c = [] := by cases c with | nil => rfl | cons a t => have := hb a (by simp) simp only [List.sum_cons] at hs omega subst c exact ⟨[], by simp [boundedCombos, hr], List.Perm.refl _⟩ · have hrlo : ¬ rem < lo := by cases c with | nil => simp_all | cons a t => have := hb a (by simp) simp only [List.sum_cons] at hs omega let n := c.count lo let t := c.filter (fun x => !(x == lo)) have hp : (List.replicate n lo ++ t).Perm c := by simpa only [List.filter_beq] using List.filter_append_perm (fun x => x == lo) c have hsum : n * lo + t.sum = rem := by simpa using hp.sum_eq.trans hs have hn : n < min (cand.count lo) (rem / lo) + 1 := by have hdiv : n ≤ rem / lo := (Nat.le_div_iff_mul_le hl).mpr (by omega) have := hc lo dsimp [n] at * omega have htlo : ∀ x ∈ t, lo + 1 ≤ x := by intro x hx have hx' : x ∈ c ∧ x ≠ lo := by simpa [t] using hx have := hb x hx'.1 omega have htc : ∀ x, t.count x ≤ cand.count x := by intro x exact (List.filter_sublist.count_le x).trans (hc x) obtain ⟨e, he, hep⟩ := ih (lo + 1) (rem - n * lo) t (by omega) (by omega) (by omega) (by omega) htc htlo refine ⟨List.replicate n lo ++ e, ?_, (List.Perm.append_left _ hep).trans hp⟩ simp only [boundedCombos, beq_iff_eq, hr, ↓reduceIte, hrlo, List.mem_flatMap, List.mem_range, List.mem_map] exact ⟨n, hn, e, he, rfl⟩ theorem enumeration_bridge (input : Input) (h : isValidInput input) (comb : List Nat) : IsValidCombination input.1 input.2 comb ↔ ∃ c ∈ allCanonicalCombos input.1 input.2, c.Perm comb := by have hpos : ∀ x ∈ input.1, 1 ≤ x := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true] at h intro x hx exact (h.1.1.2 x hx).1 rw [count_valid] constructor · rintro ⟨hs, hc⟩ apply bounded_complete input.1 (input.2 + 1) 1 input.2 comb (by omega) (by omega) (by omega) hs hc intro x hx apply hpos x exact List.count_pos_iff.mp (lt_of_lt_of_le (List.count_pos_iff.mpr hx) (hc x)) · rintro ⟨c, hm, hp⟩ obtain ⟨hs, hc, hb⟩ := bounded_sound input.1 (input.2 + 1) 1 input.2 c (by omega) hm refine ⟨hp.sum_eq.symm.trans hs, ?_⟩ intro x rw [← hp.count_eq x] exact hc x /-- On valid input the checker accepts exactly the specified outputs. -/ theorem combinationSum2_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : combinationSum2_check input result ↔ combinationSum2_spec input result := by exact root_of_bridges checker_reflection enumeration_bridge input result h /-! ### Main algorithm (impl) -/ /-- Unique valid combinations: the checker's canonical enumeration reversed into ascending lexicographic order. -/ def combinationSum2Impl (input : Input) : Output := (allCanonicalCombos input.1 input.2).reverse /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem combinationSum2Impl_correct (input : Input) (h : isValidInput input) : combinationSum2_spec input (combinationSum2Impl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([10, 1, 2, 7, 6, 1, 5], 8) #guard isValidInput ([2, 5, 2, 1, 2], 5) #guard isValidInput ([1, 2], 4) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], 1)) #guard !(isValidInput ([0], 1)) #guard !(isValidInput ([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard combinationSum2_check ([10, 1, 2, 7, 6, 1, 5], 8) [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]] #guard combinationSum2_check ([2, 5, 2, 1, 2], 5) [[1, 2, 2], [5]] #guard combinationSum2_check ([1, 2], 4) [] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(combinationSum2_check ([10, 1, 2, 7, 6, 1, 5], 8) [[1, 1, 6], [1, 2, 5]]) #guard !(combinationSum2_check ([2, 5, 2, 1, 2], 5) [[1, 2, 2], [5], [1, 2, 2]]) #guard !(combinationSum2_check ([1, 2], 4) [[1, 2]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard combinationSum2Impl ([10, 1, 2, 7, 6, 1, 5], 8) == [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]] #guard combinationSum2Impl ([2, 5, 2, 1, 2], 5) == [[1, 2, 2], [5]] #guard combinationSum2Impl ([1, 2], 4) == [] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard combinationSum2_check ([10, 1, 2, 7, 6, 1, 5], 8) (combinationSum2Impl ([10, 1, 2, 7, 6, 1, 5], 8)) #guard combinationSum2_check ([2, 5, 2, 1, 2], 5) (combinationSum2Impl ([2, 5, 2, 1, 2], 5)) #guard combinationSum2_check ([1, 2], 4) (combinationSum2Impl ([1, 2], 4)) end PCombinationSumIi