import Mathlib /-! # Subsets Ii Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. ## Constraints - 1 <= nums.length <= 10 - -10 <= nums[i] <= 10 ## Provided examples - `nums = [1, 2, 2]` → `[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]` - `nums = [0]` → `[[], [0]]` - `nums = [5]` → `[[5], []]` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 10. empty array below the minimum length) - invalid input: `nums = [-11]` ([structural] a predicate that admits -10 <= nums[i] <= 10. one below the element lower bound) - invalid input: `nums = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]` ([structural] a predicate that admits 1 <= nums.length <= 10. eleven elements, one past the maximum length) - `nums = [1, 2, 2]` → `[[], [1], [1, 2], [2], [2, 2]]` is wrong ([structural] missing tightness: every returned subset is valid but not every subset is required to appear. omits [1,2,2], so the collection is feasible but not complete) - `nums = [0]` → `[[], [0], [0]]` is wrong ([structural] duplicate subsets are permitted because the distinctness requirement is dropped. contains all true subsets plus an extra [0]) - `nums = [5]` → `[[5], [], [5, 5]]` is wrong ([structural] subsets are not required to have distinct elements. subset [5, 5] repeats an element) -/ namespace PSubsetsIi abbrev Input := List Int abbrev Output := List (List Int) /-! ### Specification helpers -/ /-- `s` is a sub-multiset of `nums`: some sublist of `nums` is a permutation of `s`. -/ def IsSubsetOf (nums s : List Int) : Prop := ∃ l : List Int, l.Sublist nums ∧ l.Perm s /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 10 elements, each between -10 and 10 inclusive. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10 && input.all (fun x => -10 ≤ x && x ≤ 10) /-! ### Ideal specification (P_spec) -/ /-- `result` lists every subset of `input`, each entry a sub-multiset of `input`, no two entries permutations of one another, and every sublist represented by some entry. -/ def uniqueSubsets_spec (input : Input) (result : Output) : Prop := (∀ s ∈ result, IsSubsetOf input s) ∧ (∀ (i j : Nat) (hi : i < result.length) (hj : j < result.length), result[i].Perm result[j] → i = j) ∧ (∀ l : List Int, l.Sublist input → ∃ s ∈ result, l.Perm s) /-! ### Decidable specification (P_check) -/ /-- Permutation equality of two lists, decided by equality of their multisets. -/ def permEq (a b : List Int) : Bool := decide (Multiset.ofList a = Multiset.ofList b) /-- Decidable `IsSubsetOf`: some member of `nums.sublists` is a permutation of `s`. -/ def isSubsetOfDec (nums s : List Int) : Bool := nums.sublists.any (fun l => permEq l s) /-- No two entries of `result` are permutations of one another. -/ def noPermDuplicates (result : List (List Int)) : Bool := (List.finRange result.length).all (fun i => (List.finRange result.length).all (fun j => (!(permEq (result.get i) (result.get j))) || (i == j))) /-- Every member of `nums.sublists` is a permutation of some entry of `result`. -/ def coversAllSublists (nums : List Int) (result : List (List Int)) : Bool := nums.sublists.all (fun l => result.any (fun s => permEq l s)) /-- Executable checker for `uniqueSubsets_spec`, with list quantifiers bounded to `input.sublists`. -/ def uniqueSubsets_check (input : Input) (result : Output) : Bool := result.all (fun s => isSubsetOfDec input s) && noPermDuplicates result && coversAllSublists input result /-- On valid input the checker accepts exactly the specified outputs. -/ theorem uniqueSubsets_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : uniqueSubsets_check input result ↔ uniqueSubsets_spec input result := by simp [uniqueSubsets_check, uniqueSubsets_spec, isSubsetOfDec, IsSubsetOf, noPermDuplicates, coversAllSublists, permEq, List.mem_sublists, Multiset.coe_eq_coe, Fin.forall_iff, and_assoc] grind only [] /-! ### Implementation helpers -/ /-- Backtracking accumulator over the sorted array: at branch offset `d` it records the current subset once (when `d = 0`), then includes each non-duplicate branch element and advances. -/ def dfs (sorted : Array Int) (start d : Nat) (cur : List Int) (acc : List (List Int)) : List (List Int) := let acc₀ := if d == 0 then cur :: acc else acc if h : start + d < sorted.size then let acc₁ := if decide (0 < d) && permEq [sorted[start + d]] [sorted[start + d - 1]] then acc₀ else dfs sorted (start + d + 1) 0 (cur ++ [sorted[start + d]]) acc₀ dfs sorted start (d + 1) cur acc₁ else acc₀ termination_by (sorted.size - start) + (sorted.size - start - d) /-- Equality of subset collections, up to collection order and permutation of each entry, since the output order is unconstrained. -/ instance beqOutput : BEq (List (List Int)) where beq a b := a.length == b.length && a.all (fun s => b.any (fun t => permEq s t)) && b.all (fun s => a.any (fun t => permEq s t)) /-! ### Main algorithm (impl) -/ /-- Unique subsets by sorting followed by depth-first backtracking that skips duplicate-value branches. -/ def subsetsWithDup (input : Input) : Output := let sorted := (input.mergeSort fun a b => decide (a ≤ b)).toArray (dfs sorted 0 0 [] []).reverse /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem subsetsWithDup_correct (input : Input) (h : isValidInput input) : uniqueSubsets_spec input (subsetsWithDup input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 2, 2] #guard isValidInput [0] #guard isValidInput [5] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [-11]) #guard !(isValidInput [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard uniqueSubsets_check [1, 2, 2] [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]] #guard uniqueSubsets_check [0] [[], [0]] #guard uniqueSubsets_check [5] [[5], []] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(uniqueSubsets_check [1, 2, 2] [[], [1], [1, 2], [2], [2, 2]]) #guard !(uniqueSubsets_check [0] [[], [0], [0]]) #guard !(uniqueSubsets_check [5] [[5], [], [5, 5]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard subsetsWithDup [1, 2, 2] == [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]] #guard subsetsWithDup [0] == [[], [0]] #guard subsetsWithDup [5] == [[5], []] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard uniqueSubsets_check [1, 2, 2] (subsetsWithDup [1, 2, 2]) #guard uniqueSubsets_check [0] (subsetsWithDup [0]) #guard uniqueSubsets_check [5] (subsetsWithDup [5]) end PSubsetsIi