Editing 3790 - subsets

Sursa: [https://www.pbinfo.ro/probleme/3790/subsets - 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.
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#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.