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 submultimi1.txt conţine pe prima linie numărul n.

Date de iesire

Fişierul de ieşire submultimi1.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

Intrare

5

Iesire

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

Intrare

-9483

Iesire

Datele introduse nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def generare_submultimi(n, subset, index):

   if index == n + 1:
       if len(subset) > 0:
           print(" ".join(map(str, subset)))
       return

   # Includem elementul la index în submulțime
   if len(subset) == 0 or abs(subset[-1] - index) > 1:
       generare_submultimi(n, subset + [index], index + 1)

   # Nu includem elementul la index în submulțime
   generare_submultimi(n, subset, index + 1)

1. Citire date de intrare

with open("submultimi1.txt", "r") as file:

   n = int(file.readline().strip())

1. Rezolvare problema

generare_submultimi(n, [], 1)

</syntaxhighlight>