// partition.cpp -- Printing out all partitions of a number n, not greater that MAXSIZE.

#include <iostream>
using namespace std;

class Partition
{
  enum {MAXSIZE = 60};
  int *base;  // Where we keep values for current row
  int maxlen; // The maximum number of positions in base.
  int length; // The number of positions currently used in base

 public:
  
  Partition(unsigned int n)
    {
      if (n < MAXSIZE)
	maxlen = n;
      else
	maxlen = MAXSIZE;
      base = new int[maxlen];
      base[0] = maxlen;
      length = 1;
    }

  ~Partition()
    {
      delete [] base;
    }

  // Prints the current content of base.
  printCurrent()
    {
      for (int k = 0; k < length; ++k)
	cout << base[k] << "  ";
      cout << endl;
    }

  // It determines the next output row.
  // Returns true if such row exists.
  // otherwise reset state to initial state and return false.
  bool findNext()
    {
      int cursor = length - 1;
      for ( ; cursor >= 0 && (base[cursor] == 1); --cursor);
      if (cursor < 0)
      {
	base[0] = maxlen;
	length = 1;
	return false;
      }
      base[cursor]--;
      int excess = length - cursor;
      int index = cursor + 1;
      while (excess >= base[cursor])
	{
	  base[index++] = base[cursor];
	  excess -= base[cursor];
	}
      if (excess > 0)
	base[index++] = excess;
      length = index;
      return true;
    }
};

void main(void)
{
  int size;
  cout << "Enter an integer: ";
  cin >> size;

  Partition p(size);

  do
      p.printCurrent();
  while  (p.findNext());
}