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 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
   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("submultimi.txt", "r") as file:

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

1. Rezolvare problema

generare_submultimi(n, [], 1)

</syntaxhighlight>