0198 - Submultimi

Cerinta

Se citește un număr natural nenul n. Să se afişeze, în ordine lexicografică, toate submulțimile nevide ale mulţimii {1,2,..,n}.

Date de intrare

Fişierul de intrare submultimiin.txt conţine pe prima linie numărul n.

Date de iesire

Fişierul de ieşire submultimiout.txt va conţine pe fiecare linie câte o submulțime, elementele unei submulțimi fiind separate printr-un spațiu.

Restrictii si precizari

• 1 ⩽ n ⩽ 10

Exemplul 1

submultimiin.txt

4

submultimiout.txt

Datele introduse corespund restrictiilor impuse

1

1 2

1 2 3

1 2 3 4

1 2 4

1 3

1 3 4

1 4

2

2 3

2 3 4

2 4

3

3 4

4

Exemplul 2

submultimiin.txt

19736

Datele introduse nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verifica_restrictii(n):

   return 1 <= n <= 10

def genereaza_submultimi(n):

   submultimi = []

   def backtrack(start, current):
       submultimi.append(current[:])

       for i in range(start, n + 1):
           current.append(i)
           backtrack(i + 1, current)
           current.pop()

   backtrack(1, [])
   return submultimi[1:]  # Excludem mulțimea vidă

1. Citire din fișierul de intrare

with open('submultimiin.txt', 'r') as file:

   n = int(file.readline())

1. Verificare restricții

if verifica_restrictii(n):

   # Generare submulțimi
   rezultat = genereaza_submultimi(n)

   # Scriere în fișierul de ieșire
   with open('submultimiout.txt', 'w') as file_out:
       for subset in rezultat:
           file_out.write(" ".join(map(str, subset)) + "\n")

else:

   print("Date de intrare nevalide.")

</syntaxhighlight>