// Program for outputting happy numbers without zeros and with digits in non-decreasing order (http://oeis.org/A124095)
#include <iostream>
#include <string>
#include <vector>
using namespace std;

#define HAPPY_NUMBERS_MAX_DIGITS 10
#define HAPPY_NUMBERS_BASE       10
#define HAPPY_NUMBERS_POWER       2

vector <unsigned long> digit_powers; // For fast happy_sum calculation
vector <bool> is_happy;              // For fast determination of whether a number is a happy number.

// possible_happy_number_sums [digits][happy_sum][lowest_digit - 1] tells if it is
// possible to make [happy_sum] with [digits] using only digits [lowest_digit] and higher.
vector <vector <vector <bool> > > possible_happy_number_sums;

char number_buffer [HAPPY_NUMBERS_MAX_DIGITS + 1]; // Used to build and output the list of happy numbers

bool isHappy (unsigned long num, unsigned long array_filled_to)
{
   if (num <= array_filled_to)
      return is_happy [num];

   unsigned long happy_sum = 0;
   while (num)
   {
      happy_sum += digit_powers [num % HAPPY_NUMBERS_BASE];
      num /= HAPPY_NUMBERS_BASE;
   }

   return isHappy (happy_sum, array_filled_to);
}

void listIncrementingHappyNumbers (char * num_buffer, char last_digit, unsigned long digits_remaining, unsigned long sum_remaining)
{
   if (digits_remaining == 0)
   {
      if (sum_remaining == 0)
      {
         *num_buffer = 0;
         cout << number_buffer << endl;
      }
   }
   else
   {
      // Try all digits greater than or equal to the last digit added
      for (char digit = last_digit; digit < HAPPY_NUMBERS_BASE; ++digit)
      {
         if ((sum_remaining >= digit_powers [digit])                                                                // digit isn't too big for the remaining sum
             && (possible_happy_number_sums [digits_remaining - 1].size () > sum_remaining - digit_powers [digit])  // Remaining sum won't be too big for remaining digits
             && possible_happy_number_sums [digits_remaining - 1][sum_remaining - digit_powers [digit]][digit - 1]) // It's possible to continue to a solution after adding this digit
         {
            *num_buffer = '0' + digit;
            listIncrementingHappyNumbers (num_buffer + 1, digit, digits_remaining - 1, sum_remaining - digit_powers [digit]);
         }
      }
   }
}

int main (int argc, char **argv)
{
   // Fill digit powers for fast happy sum calculation
   digit_powers.resize (HAPPY_NUMBERS_BASE);

   for (unsigned long digit = 0; digit < HAPPY_NUMBERS_BASE; ++digit)
      digit_powers [digit] = digit;

   for (unsigned long power = 1; power < HAPPY_NUMBERS_POWER; ++power)
      for (unsigned long digit = 0; digit < HAPPY_NUMBERS_BASE; ++digit)
         digit_powers [digit] *= digit;

   // Fill is_happy for fast determination of whether a number is happy
   is_happy.resize (HAPPY_NUMBERS_MAX_DIGITS * digit_powers [HAPPY_NUMBERS_BASE - 1] + 1);

   is_happy [0] = false;
   is_happy [1] = true;
   is_happy [2] = false;
   is_happy [3] = false;
   is_happy [4] = false;

   for (unsigned long num = 5; num < is_happy.size (); ++num)
      is_happy [num] = isHappy (num, num - 1);

   // Fill possible_happy_number_sums [digits][happy_sum][lowest_digit - 1] to tell if it is
   // possible to make [happy_sum] with [digits] using only digits [lowest_digit] and higher.
   possible_happy_number_sums.resize (HAPPY_NUMBERS_MAX_DIGITS + 1);

   possible_happy_number_sums [0].resize (1);
   possible_happy_number_sums [0][0].resize (HAPPY_NUMBERS_MAX_DIGITS - 1);
   for (unsigned long digit = 1; digit < HAPPY_NUMBERS_BASE; ++digit)
      possible_happy_number_sums [0][0][digit - 1] = true;

   for (unsigned long digits = 1; digits <= HAPPY_NUMBERS_MAX_DIGITS; ++digits)
   {
      possible_happy_number_sums [digits].resize (digits * digit_powers [HAPPY_NUMBERS_BASE - 1] + 1);
      for (unsigned long sum = 0; sum < possible_happy_number_sums [digits].size (); ++sum)
      {
         possible_happy_number_sums [digits][sum].resize (HAPPY_NUMBERS_MAX_DIGITS - 1);

         for (unsigned long digit = 1; digit < HAPPY_NUMBERS_BASE; ++digit)
         {
            bool possible = false;
            for (unsigned long next_digit = digit; !possible && (next_digit < HAPPY_NUMBERS_BASE); ++next_digit)
               if ((sum >= digit_powers [next_digit]) && (sum - digit_powers [next_digit] < possible_happy_number_sums [digits - 1].size ()))
                  possible = possible_happy_number_sums [digits - 1][sum - digit_powers [next_digit]][next_digit - 1];

            possible_happy_number_sums [digits][sum][digit - 1] = possible;
         }
      }
   }

   // Use possible_happy_number_sums as a map to build incrementing happy numbers
   for (unsigned long digits = 1; digits <= HAPPY_NUMBERS_MAX_DIGITS; ++digits)
      for (unsigned long sum = 1; sum < possible_happy_number_sums [digits].size (); ++sum)
         if (is_happy [sum])
            listIncrementingHappyNumbers (number_buffer, 1, digits, sum);

   return 0;
}