3790 - subsets

Cerinţa

Se dă șirul a1, a2, …, an de numere naturale nenule distincte. Vrem să alegem trei submulțimi X, Y și Z cu proprietățile:

submulțimile sunt nevide
orice element din șir aparține cel mult unei submulțimi
cele trei submulțimi au suma elementelor identică

De exemplu, dacă a = (1,2,3,4,5,6), atunci putem alege submulțimile: X={1,4}, Y={2,3}, Z={5}. Se observă că au toate suma elementelor egală cu 5 și că 6 nu apare în niciuna din submulțimi. O altă alegere este X={1,6}, Y={2,5}, Z={3,4} și în acest caz toate submulțimile au suma 7 și toate elementele șirului aparțin uneia dintre submulțimi.

Reținem faptul că ordinea elementelor într-o submulțime nu contează, deci X={1,4} este totuna cu X={4,1}. De asemenea, ordinea celor trei submulțimi nu contează, adică de exemplu X={1,4}, Y={2,3}, Z={5} înseamnă același triplet cu X={2,3}, Y={1,4}, Z={5}.

Să se determine numărul tripletelor de submulțimi care îndeplinesc proprietățile.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n cele numere naturale a1, a2, …, an, separate prin spații.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.", iar apoi va afișa pe ecran numărul tripletelor de submulțimi. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricţii şi precizări

3 ≤ n ≤ 10
cele n numere din șir vor fi nenule, distincte două câte două și mai mici decât 100

Exemple

Exemplul 1

Intrare: 6; 1 2 3 4 5 6
Ieșire: Datele sunt corecte.; 3

Exemplul 2

Intrare: 5; 1 2 3 4 7
Ieșire: Datele sunt corecte.; 0

Exemplul 3

Intrare: 2; 314515341535441 412351541241
Ieșire: Datele nu sunt comform restricțiilor impuse.

Rezolvare

3790 - subsets

def numara_tripleturi(n, vector):

   def verifica_suma_egala(submultimi):
       sume = []
       for submultime in submultimi:
           sume.append(sum(submultime))
       return len(set(sume)) == 1
       
   def backtracking(index, submultimi):
       nonlocal numar
       if index == n:
           if len(submultimi[0]) > 0 and len(submultimi[1]) > 0 and len(submultimi[2]) > 0 and verifica_suma_egala(submultimi):
               numar += 1
           return
       for i in range(3):
           submultimi[i].append(vector[index])
           backtracking(index + 1, submultimi)
           submultimi[i].pop()

   numar = 0
   submultimi = [[], [], []]
   backtracking(0, submultimi)
   return numar // 2

def conform_restrictiilor(n,vector):

   if not 3 <= n <= 10:
       print("Datele nu sunt conform restricțiilor impuse.")
       return False
   for x in vector:
       if x > 100 or x == 0:
           print("Datele nu sunt conform restricțiilor impuse.")
           return False
   print("Datele sunt corecte.")
   return True

if __name__ == '__main__':

   n = int(input())
   vector = list(map(int, input().split()))
   if conform_restrictiilor(n,vector) is True:
      rezultat = numara_tripleturi(n,vector)
      print(rezultat)

</syntaxhighlight>

Explicaţie cod

Funcția verifica_suma_egala primește o listă de submulțimi și verifică dacă suma elementelor din fiecare submulțime este aceeași. Pentru a face acest lucru, se calculează suma elementelor din fiecare submulțime, aceste sume fiind stocate într-o listă. Dacă această listă conține un singur element, înseamnă că suma elementelor din toate cele trei submulțimi este egală.

Funcția backtracking primește un index și o listă de submulțimi și generează toate tripleturile posibile de submulțimi care îndeplinesc criteriile impuse. Algoritmul de backtracking adaugă elemente în submulțimi în mod recursiv, începând cu primul element din vector, și verifică dacă suma elementelor din fiecare submulțime este egală. Dacă această condiție este îndeplinită pentru toate cele trei submulțimi, se incrementează numărul de tripleturi găsite.

Funcția numara_tripleturi inițializează o listă vidă pentru fiecare submulțime și apelează funcția backtracking pentru a genera toate tripleturile de submulțimi. Numărul de tripleturi găsite este returnat împărțit la 2 pentru a elimina duplicatele, deoarece un triplet de submulțimi poate fi reprezentat într-un mod diferit (fiecare submulțime poate fi permutată).

Funcția conform_restrictiilor verifică dacă datele de intrare sunt conforme cu restricțiile impuse și returnează True dacă acest lucru este adevărat. Datele de intrare trebuie să aibă o dimensiune cuprinsă între 3 și 10, inclusiv, iar fiecare element din vector trebuie să fie mai mic sau egal cu 100 și diferit de 0.