import Mathlib /-! # Combination Sum Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different. The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input. ## Constraints - 1 <= candidates.length <= 30 - 2 <= candidates[i] <= 40 - All elements of candidates are distinct. - 1 <= target <= 40 ## Provided examples - `candidates = [2, 3, 6, 7], target = 7` → `[[2, 2, 3], [7]]` - `candidates = [2, 3, 5], target = 8` → `[[2, 2, 2, 2], [2, 3, 3], [3, 5]]` - `candidates = [2], target = 1` → `[]` ## Synthesized negative examples - invalid input: `candidates = [], target = 5` ([structural] a predicate that admits 1 <= candidates.length <= 30. empty where at least one element is required) - invalid input: `candidates = [1], target = 5` ([structural] a predicate that admits 2 <= candidates[i] <= 40. one below the stated minimum candidate value) - invalid input: `candidates = [2, 2], target = 3` ([structural] a predicate that admits All elements of candidates are distinct.. duplicate where a distinct set is required) - `candidates = [2, 3, 6, 7], target = 7` → `[[2, 2, 2, 2], [2, 3, 3], [2, 6]]` is wrong ([structural] target comparison is off by one. every combination sums to 8, one above the true target) - `candidates = [2, 3, 5], target = 8` → `[]` is wrong ([structural] return all omitted. Empty satisfies every property vacuously if completeness omitted) - `candidates = [2], target = 1` → `[[2]]` is wrong ([structural] soundness clause omitted. not_optimal inapplicable; first candidate accepted without sum check) -/ namespace PCombinationSum abbrev Input := (List Nat) × (Nat) abbrev Output := List (List Nat) /-! ### Specification helpers -/ /-- `combo` is a combination for `candidates` and `target`: every element is in `candidates` and the elements sum to `target`. -/ def IsCombination (candidates : List Nat) (target : Nat) (combo : List Nat) : Prop := (∀ x ∈ combo, x ∈ candidates) ∧ combo.sum = target /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 30 distinct candidates, each between 2 and 40, and a target between 1 and 40. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 30 && input.1.all (fun c => 2 ≤ c && c ≤ 40) && decide input.1.Nodup && 1 ≤ input.2 && input.2 ≤ 40 /-! ### Ideal specification (P_spec) -/ /-- `result` is exactly the combinations of `input` up to order: each element is a combination, no two are permutations, and every combination permutes some element. -/ def combinationSum_spec (input : Input) (result : Output) : Prop := (∀ combo ∈ result, IsCombination input.1 input.2 combo) ∧ result.Pairwise (fun a b => ¬ a.Perm b) ∧ ∀ combo, IsCombination input.1 input.2 combo → ∃ r ∈ result, combo.Perm r /-! ### Decidable specification (P_check) -/ /-- Enumerates every combination as candidate runs in candidate order without exceeding `target`. -/ def candidateCombos (candidates : List Nat) (target : Nat) : List (List Nat) := if target = 0 then [[]] else match candidates with | [] => [] | c :: [] => if c = 0 then [] else if target % c = 0 then [List.replicate (target / c) c] else [] | c :: cs => let rest := candidateCombos cs (List.range (target / c + 1)).flatMap (fun count => (rest (target - count * c)).map (fun combo => List.replicate count c ++ combo)) /-- Executable form of `IsCombination`. -/ def isCombinationValue (candidates : List Nat) (target : Nat) (combo : List Nat) : Bool := combo.all (fun x => decide (x ∈ candidates)) && decide (combo.sum = target) /-- Checks whether some output element is a permutation of `combo`. -/ def appearsUpToPerm (combo : List Nat) (result : Output) : Bool := result.any (fun candidate => decide (combo.Perm candidate)) /-- Checks that no two distinct output elements are permutations. -/ def noPermPairs (result : Output) : Bool := decide (result.Pairwise (fun first second => ¬ first.Perm second)) /-- Executable checker for `combinationSum_spec` over the enumerated combinations. -/ def combinationSum_check (input : Input) (result : Output) : Bool := result.all (fun combo => isCombinationValue input.1 input.2 combo) && noPermPairs result && (candidateCombos input.1 input.2).all (fun combo => appearsUpToPerm combo result) theorem root_of_bridges (sound : ∀ (cs : List Nat) (t : Nat), (∀ x ∈ cs, 0 < x) → ∀ r ∈ candidateCombos cs t, IsCombination cs t r) (complete : ∀ (cs : List Nat) (t : Nat), (∀ x ∈ cs, 0 < x) → ∀ r, IsCombination cs t r → ∃ s ∈ candidateCombos cs t, r.Perm s) (input : Input) (result : Output) (h : isValidInput input) : combinationSum_check input result ↔ combinationSum_spec input result := by have hp : ∀ x ∈ input.1, 0 < x := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true] at h intro x hx have := h.1.1.1.2 x hx omega simp only [combinationSum_check, Bool.and_eq_true, List.all_eq_true, isCombinationValue, decide_eq_true_eq, noPermPairs, appearsUpToPerm, List.any_eq_true, combinationSum_spec, IsCombination] constructor · rintro ⟨⟨hs, hn⟩, hc⟩ refine ⟨hs, hn, ?_⟩ intro r hr obtain ⟨s, hs', hrs⟩ := complete input.1 input.2 hp r hr obtain ⟨q, hq, hsq⟩ := hc s hs' exact ⟨q, hq, hrs.trans hsq⟩ · rintro ⟨hs, hn, hc⟩ exact ⟨⟨hs, hn⟩, fun s hs' => hc s (sound input.1 input.2 hp s hs')⟩ theorem combos_complete (cs : List Nat) (t : Nat) (hp : ∀ x ∈ cs, 0 < x) (r : List Nat) (hr : IsCombination cs t r) : ∃ s ∈ candidateCombos cs t, r.Perm s := by induction cs generalizing t r with | nil => have he : r = [] := by cases r with | nil => rfl | cons a r => have := hr.1 a (by simp); simp at this subst r have ht : t = 0 := by simpa using hr.2.symm subst t exact ⟨[], by simp [candidateCombos], List.Perm.refl _⟩ | cons c cs ih => have hc : 0 < c := hp c (by simp) by_cases ht : t = 0 · have he : r = [] := by cases r with | nil => rfl | cons a r => have ha := hp a (hr.1 a (by simp)) have hs := hr.2 simp only [List.sum_cons] at hs omega subst r exact ⟨[], by cases cs <;> simp [candidateCombos, ht], List.Perm.refl _⟩ · cases cs with | nil => have he : r = List.replicate r.length c := List.eq_replicate_length.mpr (by simpa using hr.1) have hs : r.length * c = t := by have := hr.2 rw [he, List.sum_replicate] at this simpa using this have hm : t % c = 0 := by rw [← hs]; simp have hd : t / c = r.length := by rw [← hs]; exact Nat.mul_div_cancel _ hc refine ⟨r, ?_, List.Perm.refl _⟩ simp only [candidateCombos, ht, if_false, Nat.ne_of_gt hc, hm, if_true] simp [hd, ← he] | cons d ds => let a := r.filter (fun x => decide (x = c)) let s := r.filter (fun x => !decide (x = c)) have he : a = List.replicate a.length c := by apply List.eq_replicate_length.mpr intro x hx simpa [a] using (List.mem_filter.mp hx).2 have hperm : r.Perm (List.replicate a.length c ++ s) := by have hh := (List.filter_append_perm (fun x => decide (x = c)) r).symm change r.Perm (a ++ s) at hh rwa [he] at hh have hs : ∀ x ∈ s, x ∈ d :: ds := by intro x hx have hm := List.mem_filter.mp hx have hin := hr.1 x hm.1 simp only [List.mem_cons] at hin have hn : x ≠ c := by simpa using hm.2 rcases hin with h | h · exact False.elim (hn h) · simpa only [List.mem_cons] using h have hsum : a.length * c + s.sum = t := by have hh := hperm.sum_eq rw [List.sum_append, List.sum_replicate] at hh simpa [hr.2] using hh.symm have hb : a.length ≤ t / c := (Nat.le_div_iff_mul_le hc).mpr (by omega) have hp' : ∀ x ∈ d :: ds, 0 < x := fun x hx => hp x (by simp [hx]) obtain ⟨q, hq, hsq⟩ := ih (t - a.length * c) hp' s ⟨hs, by omega⟩ refine ⟨List.replicate a.length c ++ q, ?_, hperm.trans ((List.Perm.refl _).append hsq)⟩ simp only [candidateCombos, ht, if_false, List.mem_flatMap] refine ⟨a.length, List.mem_range.mpr (by omega), ?_⟩ exact List.mem_map.mpr ⟨q, hq, rfl⟩ theorem combos_sound : ∀ (cs : List Nat) (t : Nat), (∀ x ∈ cs, 0 < x) → ∀ r ∈ candidateCombos cs t, IsCombination cs t r := by intro cs induction cs with | nil => intro t hpos r hr by_cases ht : t = 0 · subst t simp [candidateCombos] at hr subst r simp [IsCombination] · simp [candidateCombos, ht] at hr | cons c cs ih => intro t hpos r hr have hc : 0 < c := hpos c (by simp) have hcs : ∀ x ∈ cs, 0 < x := by intro x hx exact hpos x (by simp [hx]) by_cases ht : t = 0 · subst t cases cs <;> simp [candidateCombos] at hr <;> subst r <;> simp [IsCombination] · cases cs with | nil => by_cases hm : t % c = 0 · simp [candidateCombos, ht, hc.ne', hm] at hr subst r constructor · intro x hx simp only [List.mem_replicate] at hx simp [hx] · simp only [List.sum_replicate_nat] simpa [hm] using Nat.mod_add_div' t c · simp [candidateCombos, ht, hc.ne', hm] at hr | cons d ds => simp only [candidateCombos, ht, if_false, List.mem_flatMap, List.mem_range, List.mem_map] at hr rcases hr with ⟨count, hcount, combo, hcombo, rfl⟩ have htail := ih (t - count * c) hcs combo hcombo rcases htail with ⟨hmem, hsum⟩ constructor · intro x hx simp only [List.mem_append, List.mem_replicate] at hx rcases hx with hx | hx · simp [hx] · exact List.mem_cons_of_mem c (hmem x hx) · simp only [List.sum_append, List.sum_replicate_nat, hsum] have hlediv : count ≤ t / c := Nat.lt_succ_iff.mp hcount have hmul : count * c ≤ t := (Nat.le_div_iff_mul_le hc).mp hlediv exact Nat.add_sub_of_le hmul /-- On valid input the checker accepts exactly the specified outputs. -/ theorem combinationSum_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : combinationSum_check input result ↔ combinationSum_spec input result := by exact root_of_bridges combos_sound combos_complete input result h /-! ### Main algorithm (impl) -/ /-- Combinations by backtracking over per-candidate multiplicities via `candidateCombos`, reversed to the frozen order. -/ def combinationSumUnlimited (input : Input) : Output := (candidateCombos input.1 input.2).reverse /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem combinationSumUnlimited_correct (input : Input) (h : isValidInput input) : combinationSum_spec input (combinationSumUnlimited input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([2, 3, 6, 7], 7) #guard isValidInput ([2, 3, 5], 8) #guard isValidInput ([2], 1) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], 5)) #guard !(isValidInput ([1], 5)) #guard !(isValidInput ([2, 2], 3)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard combinationSum_check ([2, 3, 6, 7], 7) [[2, 2, 3], [7]] #guard combinationSum_check ([2, 3, 5], 8) [[2, 2, 2, 2], [2, 3, 3], [3, 5]] #guard combinationSum_check ([2], 1) [] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(combinationSum_check ([2, 3, 6, 7], 7) [[2, 2, 2, 2], [2, 3, 3], [2, 6]]) #guard !(combinationSum_check ([2, 3, 5], 8) []) #guard !(combinationSum_check ([2], 1) [[2]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard combinationSumUnlimited ([2, 3, 6, 7], 7) == [[2, 2, 3], [7]] #guard combinationSumUnlimited ([2, 3, 5], 8) == [[2, 2, 2, 2], [2, 3, 3], [3, 5]] #guard combinationSumUnlimited ([2], 1) == [] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard combinationSum_check ([2, 3, 6, 7], 7) (combinationSumUnlimited ([2, 3, 6, 7], 7)) #guard combinationSum_check ([2, 3, 5], 8) (combinationSumUnlimited ([2, 3, 5], 8)) #guard combinationSum_check ([2], 1) (combinationSumUnlimited ([2], 1)) end PCombinationSum