3197 - Partitii Nr 2

Cerința

Se dă un număr natural n. Determinați, în ordine lexicografică, toate modalitățile de a-l scrie pe n ca sumă de numere naturale ordonate strict crescător astfel încât diferența dintre doi termeni consecutivi ai sumei să fie cel mult 2.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran pe fiecare linie câte un șir de numere naturale ordonate strict crescător, separate prin câte un spațiu. Suma numerelor din fiecare șir este n, iar diferența dintre oricare doi termeni consecutivi este cel mult 2. Șirurile vor fi afișate în ordine lexicografică.

Restricții și precizări

1 ≤ n ≤ 300 ==Exemplu==: Intrare

21 Ieșire

1 2 3 4 5 6 1 2 4 6 8 1 3 4 6 7 2 3 4 5 7 3 4 6 8 3 5 6 7 5 7 9 6 7 8 10 11 21

Rezolvare

def partitii(n):

   def backtracking(curent, suma, start):
       if suma == n:
           solutii.append(list(curent))
           return
       for i in range(start, n - suma + 1):
           if len(curent) == 0 or abs(curent[-1] - i) <= 2:
               curent.append(i)
               backtracking(curent, suma + i, i + 1)
               curent.pop()

   solutii = []
   backtracking([], 0, 1)
   return solutii

if __name__ == "__main__":

   # Citim datele de intrare
   n = int(input())

   # Calculăm și afișăm rezultatul
   rezultat = partitii(n)
   for solutie in rezultat:
       print(*solutie)

python partitiinumar2.py