1286 - submultimi1

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} pentru care diferența dintre oricare două elemente este mai mare decât 1.

Date de intrare

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

Date de iesire

Fişierul de ieşire submultimi1out.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
• elementele fiecărei submulțimi vor fi afișate în ordine crescătoare

Exemplul 1

submultimi1in.txt

5

submultimi1out.txt

Datele introduse corespund restrictiilor impuse

1

1 3

1 3 5

1 4

1 5

2

2 4

2 5

3

3 5

4

5

Exemplul 2

submultimi1in.txt

-9483

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):
            if not current or abs(current[-1] - i) > 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('submultimi1in.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('submultimi1out.txt', 'w') as file_out:
        for subset in rezultat:
            file_out.write(" ".join(map(str, subset)) + "\n")
else:
    print("Date de intrare nevalide.")