fork download
copy 
  1. def func():
  2.     global s, n
  3.     def init():
  4.         if level == 1:
  5.             stack[level] = 0
  6.         else:
  7.             stack[level] = stack[level-1]-1
  8.  
  9.     def succ():
  10.         global s
  11.         if stack[level] < (n - s):
  12.             stack[level] += 1
  13.             return True
  14.         else:
  15.             s = s - stack[level-1]
  16.             return False
  17.  
  18.     def valid():
  19.         global s
  20.         if stack[level] <= n - s:
  21.             s = s + stack[level]
  22.             return True
  23.         return False
  24.  
  25.     def printf():
  26.         global s
  27.         for i in range(1, level+1):
  28.             print(stack[i], end = " ")
  29.         s -= stack[level]
  30.         print()
  31.  
  32.     def sol():
  33.         return s == n
  34.  
  35.     def backtracking():
  36.         global level, s
  37.         s = 0
  38.         level = 1
  39.         init()
  40.         while level > 0:
  41.             h = True
  42.             v = False
  43.             while h is True and v is False:
  44.                 h = succ()
  45.                 if h is True:
  46.                     v = valid()
  47.             if h is True:
  48.                 if sol() is True:
  49.                     printf()
  50.                 else:
  51.                     level+=1
  52.                     init()
  53.             else:
  54.                 level-=1
  55.  
  56.     n = 4
  57.     stack = [0] * (n+1)
  58.     backtracking()
  59.  
  60. func()
  61.  
Success #stdin #stdout 0.03s 9656KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 1 1 1 
1 1 2 
1 3 
2 2 
4
https://ideone.com/mTFfYg
Partition of a number based on recursion
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!