fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int n,
  6.     sum,
  7.     stack[ 101 ],
  8.     level;
  9.  
  10. void solve(int level) {
  11.  
  12.      if(sum == n) {
  13.  
  14.        for(int i = 1; i < level; ++i) {
  15.  
  16.          cout<<stack[i]<<" ";
  17.  
  18.        }
  19.  
  20.        cout<<endl;
  21.  
  22.      } else {
  23.  
  24.         if(level==1) stack[level] = 0;
  25.  
  26.         else stack[level] = stack[level-1] - 1;
  27.  
  28.         while(stack[level] + sum < n) {
  29.  
  30.               stack[level]+=1;
  31.  
  32.               sum += stack[level];
  33.  
  34.               solve(level+1);
  35.  
  36.               sum -= stack[level];
  37.         }
  38.      }
  39. }
  40.  
  41. void init() {
  42.     if(level==1)
  43.      stack[level] = 0;
  44.     else stack[level] = stack[level-1] - 1;
  45. }
  46.  
  47. int succ() {
  48.  
  49.     if(stack[level] + sum < n) {
  50.        stack[level]++;
  51.        return 1;
  52.     }  else {
  53.        sum -= stack[level-1];
  54.        return 0;
  55.     }
  56. }
  57.  
  58. int valid() {
  59.  
  60.     if( stack[level] + sum <= n ) {
  61.  
  62.         sum += stack[ level ];
  63.  
  64.        return 1;
  65.     }
  66.  
  67.     return 0;
  68. }
  69.  
  70. int sol() {
  71.  
  72.   return sum == n;
  73. }
  74.  
  75. void print() {
  76.  
  77.     for(int i = 1; i <= level; ++i) {
  78.  
  79.       cout<<stack[i]<<" ";
  80.     }
  81.  
  82.     cout<<endl;
  83.  
  84.     sum -= stack[level];
  85. }
  86.  
  87. void bk() {
  88.  
  89.   level = 1;
  90.  
  91.   init();
  92.  
  93.   while( level > 0 ) {
  94.  
  95.       int h,v;
  96.  
  97.       h = 1;
  98.       v = 0;
  99.       while(h && !v) {
  100.         h = succ();
  101.         if(h) {
  102.           v = valid();
  103.         }
  104.       }
  105.  
  106.       if(h) {
  107.         if(sol()) {
  108.           print();
  109.         } else {
  110.           level++;
  111.           init();
  112.         }
  113.       } else {
  114.         level--;
  115.       }
  116.   }
  117. }
  118.  
  119. int main(int argc, char const *argv[]) {
  120.  
  121.   sum = 0;
  122.  
  123.   cin>>n;
  124.  
  125.   solve(1);
  126.  
  127.  // bk();
  128.  
  129.   return 0;
  130.  
  131. }
  132.  
Success #stdin #stdout 0.01s 5432KB
comments (?)
stdin
copy 
5
stdout
copy 
1 1 1 1 1 
1 1 1 2 
1 1 3 
1 2 2 
1 4 
2 3 
5
https://ideone.com/odHFzF
Partitions of an Integer Rec & Iter
language:
C++ (gcc 8.3)
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!