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

<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>