fork download
copy 
  1. #include <stddef.h>
  2. #include <assert.h>
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. typedef unsigned char uchar;
  7. typedef unsigned int uint;
  8.  
  9. typedef struct tAddend
  10. {
  11.   struct tAddend* pPrev;
  12.   uint Value;
  13. } tAddend;
  14.  
  15. void findRecursiveSolution(uint n, uint maxAddend, tAddend* pPrevAddend)
  16. {
  17.   uint i;
  18.  
  19.   for (i = maxAddend; ; i--)
  20.   {
  21.     if (n == 0)
  22.     {
  23.       while (pPrevAddend != NULL)
  24.       {
  25.         printf("+%u", pPrevAddend->Value);
  26.         pPrevAddend = pPrevAddend->pPrev;
  27.       }
  28.       printf("\n");
  29.       return;
  30.     }
  31.  
  32.     if (n >= i && i > 0)
  33.     {
  34.       tAddend a;
  35.       a.pPrev = pPrevAddend;
  36.       a.Value = i;
  37.       findRecursiveSolution(n - i, i - 1, &a);
  38.     }
  39.  
  40.     if (i <= 1)
  41.     {
  42.       break;
  43.     }
  44.   }
  45. }
  46.  
  47. void printDynamicSolution(uchar** pTable, uint n, uint idx, uint sum, tAddend* pPrevAddend)
  48. {
  49.   uchar el = pTable[idx][sum];
  50.  
  51.   assert((el != 0) && (el != 5) && (el != 7));
  52.  
  53.   if (el & 2) // 2,3,6 - other(s)
  54.   {
  55.     printDynamicSolution(pTable,
  56.                          n,
  57.                          idx - 1,
  58.                          sum,
  59.                          pPrevAddend);
  60.   }
  61.  
  62.   if (el & 4) // self + other(s)
  63.   {
  64.     tAddend a;
  65.     a.pPrev = pPrevAddend;
  66.     a.Value = idx + 1;
  67.  
  68.     printDynamicSolution(pTable,
  69.                          n,
  70.                          idx - 1,
  71.                          sum - (idx + 1),
  72.                          &a);
  73.   }
  74.  
  75.   if (el & 1) // self, found a solution
  76.   {
  77.     tAddend a;
  78.     a.pPrev = pPrevAddend;
  79.     a.Value = idx + 1;
  80.  
  81.     pPrevAddend = &a;
  82.     while (pPrevAddend != NULL)
  83.     {
  84.       printf("+%u", pPrevAddend->Value);
  85.       pPrevAddend = pPrevAddend->pPrev;
  86.     }
  87.     printf("\n");
  88.   }
  89. }
  90.  
  91. void findDynamicSolution(uint n)
  92. {
  93.   uchar** table;
  94.   uint i, j;
  95.  
  96.   if (n == 0)
  97.   {
  98.     return;
  99.   }
  100.  
  101.   // Allocate the DP table
  102.  
  103.   table = malloc(sizeof(uchar*) * n);
  104.  
  105.   if (table == NULL)
  106.   {
  107.     printf("not enough memory\n");
  108.     return;
  109.   }
  110.  
  111.   for (i = 0; i < n; i++)
  112.   {
  113.     table[i] = malloc(n + 1);
  114.  
  115.     if (table[i] == NULL)
  116.     {
  117.       while (i > 0)
  118.       {
  119.         free(table[--i]);
  120.       }
  121.  
  122.       free(table);
  123.       printf("not enough memory\n");
  124.       return;
  125.     }
  126.   }
  127.  
  128.   // Fill in the DP table
  129.  
  130.   for (i = 0; i < n; i++)
  131.   {
  132.     for (j = 0; j <= n; j++)
  133.     {
  134.       if (i == 0)
  135.       {
  136.         table[i][j] = (i + 1 == j); // self
  137.       }
  138.       else
  139.       {
  140.         table[i][j] = (i + 1 == j) + // self
  141.           2 * (table[i - 1][j] != 0) + // other(s)
  142.           4 * ((j >= i + 1) && (table[i - 1][j - (i + 1)] != 0)); // self + other(s)
  143.       }
  144.     }
  145.   }
  146.  
  147.   printDynamicSolution(table, n, n - 1, n, NULL);
  148.  
  149.   for (i = 0; i < n; i++)
  150.   {
  151.     free(table[i]);
  152.   }
  153.  
  154.   free(table);
  155. }
  156.  
  157. int main(int argc, char** argv)
  158. {
  159.   uint n;
  160.  
  161.   if (argc != 2 || sscanf(argv[1], "%u", &n) != 1)
  162.   {
  163.     n = 10;
  164.   }
  165.  
  166.   printf("Recursive Solution:\n");
  167.   findRecursiveSolution(n, n, NULL);
  168.  
  169.   printf("\nDynamic Solution:\n");
  170.   findDynamicSolution(n);
  171.  
  172.   return 0;
  173. }
  174.  
Success #stdin #stdout 0.01s 1852KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Recursive Solution:
+10
+1+9
+2+8
+3+7
+1+2+7
+4+6
+1+3+6
+1+4+5
+2+3+5
+1+2+3+4

Dynamic Solution:
+1+2+3+4
+2+3+5
+1+4+5
+1+3+6
+4+6
+1+2+7
+3+7
+2+8
+1+9
+10
https://ideone.com/wN4Il
language:
C99 (gcc 8.3)
created:
12 years ago
visibility:
public

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!