fork download
copy 
  1. def partition():
  2.     global n, sum, stack
  3.     sum = 0
  4.     n = int(input("n="))
  5.     stack = [0]*(n+1)
  6.  
  7.     def init(level):
  8.         if level == 1:
  9.             stack[level] = 0
  10.         else:
  11.             stack[level] = stack[level-1] - 1
  12.     def succ(level) -> bool:
  13.  
  14.         global sum
  15.         if stack[level] < n - sum:
  16.             stack[level] +=1
  17.             return True
  18.         else:
  19.             sum -= stack[level-1]
  20.             return False
  21.  
  22.     def valid(level) -> bool:
  23.         global sum
  24.         if stack[level] <= n - sum:
  25.             sum += stack[level]
  26.             return True
  27.         return False
  28.  
  29.     def sol(level) -> bool:
  30.         return sum == n
  31.  
  32.     def printf(level):
  33.         global sum
  34.         for i in range(1, level+1):
  35.             print(stack[i], end = " ")
  36.         print()
  37.         sum -= stack[level]
  38.  
  39.     def solve(level):
  40.         init(level)
  41.         while succ(level) is True:
  42.             if valid(level) == True:
  43.                 if sol(level) == True:
  44.                     printf(level)
  45.                 else:
  46.                     solve(level+1)
  47.     solve(1)
  48. partition()
  49.  
Success #stdin #stdout 0.04s 9844KB
comments (?)
stdin
copy 
5
stdout
copy 
n=1 1 1 1 1 
1 1 1 2 
1 1 3 
1 2 2 
1 4 
2 3 
5
https://ideone.com/q2tGzj
Partitions Integers Rec
language:
Python 3 (python  3.9.5)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!