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

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ă

# Citire din fișierul de intrare
with open('submultimiin.txt', 'r') as file:
    n = int(file.readline())

# 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.")