import Mathlib /-! # Subsets Given an integer array nums of unique elements, 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 - All the numbers of nums are unique. ## Provided examples - `nums = [1, 2, 3]` → `[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]` - `nums = [0]` → `[[], [0]]` - `nums = [1]` → `[[], [1]]` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 10. empty where at least one element is required) - invalid input: `nums = [-11]` ([structural] a predicate that admits -10 <= nums[i] <= 10. -11 is one below the stated minimum) - invalid input: `nums = [1, 1]` ([structural] a predicate that admits All the numbers of nums are unique.. duplicate where uniqueness is required) - `nums = [1, 2, 3]` → `[[], [1], [2], [1, 2], [3], [1, 3], [2, 3]]` is wrong ([structural] not all subsets are required to appear. full set omitted but all listed are valid) - `nums = [0]` → `[[], [0], [0, 0]]` is wrong ([structural] subsets are not required to contain distinct elements. adds [0,0], which repeats the only element) - `nums = [1]` → `[[], [1], [2]]` is wrong ([structural] listed subsets are not required to be drawn from nums. both true subsets present; 2 is unreachable) -/ namespace PSubsets abbrev Input := List Int abbrev Output := List (List Int) /-! ### Specification helpers -/ /-- `s` represents a subset of `nums`: it has no duplicate elements and every element occurs in `nums`. -/ def IsSubsetList (nums : List Int) (s : List Int) : Prop := s.Nodup ∧ s ⊆ nums /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 10 elements, each between -10 and 10, all distinct. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10 && input.all (fun x => -10 ≤ x && x ≤ 10) && decide input.Nodup /-! ### Ideal specification (P_spec) -/ /-- `result` is the power set of `input` up to permutation: every member is a subset-list of `input`, no two positions hold permutation-equal lists, and every subset-list of `input` is a permutation of some member. -/ def subsets_spec (input : Input) (result : Output) : Prop := (∀ s ∈ result, IsSubsetList input s) ∧ result.Pairwise (fun a b => ¬ List.Perm a b) ∧ ∀ s : List Int, IsSubsetList input s → ∃ r ∈ result, List.Perm r s /-! ### Decidable specification (P_check) -/ /-- Decidability of `IsSubsetList`: `Nodup` and the elementwise membership unfolding of `List.Subset` are both decidable over `Int`. -/ instance decidableIsSubsetList (nums s : List Int) : Decidable (IsSubsetList nums s) := inferInstanceAs (Decidable (s.Nodup ∧ ∀ x ∈ s, x ∈ nums)) /-- Executable checker for `subsets_spec`: the quantification over all subset-lists is reshaped into enumeration over `input.sublists`, the permutation representatives of subset-lists. -/ def subsets_check (input : Input) (result : Output) : Bool := decide (∀ s ∈ result, IsSubsetList input s) && decide (result.Pairwise (fun a b => ¬ List.Perm a b)) && input.sublists.all (fun s => result.any (fun r => decide (List.Perm r s))) theorem subsets_nodup_of_valid {input : Input} (h : isValidInput input) : input.Nodup := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq] at h exact h.2 theorem subsets_mem_sublists_isSubsetList {input : Input} (hnd : input.Nodup) {t : List Int} (ht : t ∈ input.sublists) : IsSubsetList input t := by rw [List.mem_sublists] at ht exact ⟨ht.nodup hnd, ht.subset⟩ theorem subsets_exists_sublist_perm {input : Input} {s : List Int} (hs : IsSubsetList input s) : ∃ t ∈ input.sublists, List.Perm t s := by obtain ⟨hnodup, hsub⟩ := hs obtain ⟨t, htp, hts⟩ := List.subperm_of_subset hnodup hsub exact ⟨t, List.mem_sublists.mpr hts, htp⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem subsets_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : subsets_check input result ↔ subsets_spec input result := by have hnd : input.Nodup := subsets_nodup_of_valid h simp only [subsets_check, subsets_spec, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, List.any_eq_true] constructor · rintro ⟨⟨h1, h2⟩, h3⟩ refine ⟨h1, h2, ?_⟩ intro s hs obtain ⟨t, ht, htp⟩ := subsets_exists_sublist_perm hs obtain ⟨r, hr, hrp⟩ := h3 t ht exact ⟨r, hr, hrp.trans htp⟩ · rintro ⟨h1, h2, h3⟩ refine ⟨⟨h1, h2⟩, ?_⟩ intro t ht obtain ⟨r, hr, hrp⟩ := h3 t (subsets_mem_sublists_isSubsetList hnd ht) exact ⟨r, hr, hrp⟩ /-! ### Implementation helpers -/ /-- Alternates the elements of two lists, `interleave [a₁, a₂, …] [b₁, b₂, …] = [a₁, b₁, a₂, b₂, …]`. -/ def interleave : List (List Int) → List (List Int) → List (List Int) := List.interleave /-! ### Main algorithm (impl) -/ /-- Power set by the inclusion/exclusion recursion, ordered by binary counting: the subsets without the head are interleaved with those carrying it, so index bit `i` selects element `i`. -/ def generateSubsets (input : Input) : Output := match input with | [] => [[]] | x :: xs => interleave (generateSubsets xs) ((generateSubsets xs).map (x :: ·)) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem generateSubsets_correct (input : Input) (h : isValidInput input) : subsets_spec input (generateSubsets input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 2, 3] #guard isValidInput [0] #guard isValidInput [1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [(-11)]) #guard !(isValidInput [1, 1]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard subsets_check [1, 2, 3] [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] #guard subsets_check [0] [[], [0]] #guard subsets_check [1] [[], [1]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(subsets_check [1, 2, 3] [[], [1], [2], [1, 2], [3], [1, 3], [2, 3]]) #guard !(subsets_check [0] [[], [0], [0, 0]]) #guard !(subsets_check [1] [[], [1], [2]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard generateSubsets [1, 2, 3] == [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] #guard generateSubsets [0] == [[], [0]] #guard generateSubsets [1] == [[], [1]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard subsets_check [1, 2, 3] (generateSubsets [1, 2, 3]) #guard subsets_check [0] (generateSubsets [0]) #guard subsets_check [1] (generateSubsets [1]) end PSubsets