fork download
copy 
  1. #include <stdio.h>
  2. #define DIM 100
  3.  
  4. int stack[DIM],
  5.     N,
  6.     level,
  7.     s;
  8.  
  9. void init(){
  10.      if(level == 1) {
  11.        stack[level] = 0;
  12.      } else {
  13.        stack[level] = stack[level-1] - 1;
  14.      }
  15. }
  16.  
  17. int succ() {
  18.     if(stack[level] < N - s) {
  19.        stack[level]++;
  20.        return 1;
  21.     } else {
  22.        s -= stack[level-1];
  23.        return 0;
  24.     }
  25. }
  26.  
  27. int valid() {
  28.  
  29.     if(stack[level] <= N - s) {
  30.        s = s + stack[level];
  31.        return 1;
  32.     }
  33.     return 0;
  34. }
  35.  
  36. void print() {
  37.      //converted to string
  38.      char out[10];
  39.           int k = 0;
  40.           for(int i = 1; i <= level;i++) {
  41.               out[k++] = stack[i] + '0';
  42.               out[k++] = '+';
  43.           }
  44.           out[--k] = '\0';
  45.           s -= stack[level];
  46.           printf("%s", out);
  47.      printf("\n");
  48. }
  49.  
  50. int sol() {
  51.     return s == N;
  52. }
  53.  
  54. void bk() {
  55.      level = 1;
  56.      init();
  57.  
  58.      while(level > 0) {
  59.           int hs = 1, iv = 0;
  60.           while(hs && !iv) {
  61.                 hs = succ();
  62.                 if(hs) {
  63.                   iv = valid();
  64.                 }
  65.           }
  66.           if(hs) {
  67.             if(sol()) print();
  68.                else {
  69.                  level++;
  70.                  init();
  71.                }
  72.           } else {
  73.             level--;
  74.           }
  75.      }
  76. }
  77.  
  78. int main(int argc, char const *argv[]) {
  79.   scanf("%d", &N);
  80.   ;
  81.   bk()
  82.   ;
  83.   return 0;
  84. }
  85.  
Success #stdin #stdout 0s 5360KB
comments (?)
stdin
copy 
4
stdout
copy 
1+1+1+1
1+1+2
1+3
2+2
4
https://ideone.com/MbAg5f
Partitions of a number.
language:
C (gcc 8.3)
created:
3 years 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!