#include <stdio.h>
#include <stdlib.h>

/**
 * Finds the shortest sequence of positive squares that adds up to some
 * positive integer n given on the command line.  Backtracking!
 */

void find_sum(int target, int partial[], int num_partial, int sum_partial, int min, int best[], int *shortest);

int main(int argc, char *argv[])
{
  if (argc < 2)
    {
      printf("USAGE: %s n\n", argv[0]);
      return 1;
    }
				   
  int n = atoi(argv[1]);

  if (n < 1)
    {
      printf("%s: n must be a positive integer; was %s\n", argv[0], argv[1]);
      return 1;
    }

  int squares[n]; // the partial solution we will build up
  int best[n]; // the best solution
  int shortest = n + 1; // we know 1 + 1 + ... + 1 works and is better than this, so this *will* get updated

  // generally, pass
  // 1) information about what we're trying to achieve (sum of n)
  // 2) the partial solution (squares, initially with 0 items in)
  // 3) some bookkeeping info about the partial solution to speed things up (sum is 0)
  // 4) some information to restrict how to fill out partial solution (fill partial with squares >= 1 [no restriction initially])
  // 5) the best solution so far (best, with shortest items in)
  find_sum(n, squares, 0, 0, 1, best, &shortest);

  for (int i = 0; i < shortest; i++)
    {
      printf("%d ", best[i]);
    }
  printf("\n");
}

void find_sum(int target, int partial[], int num_partial, int sum_partial, int min, int best[], int *shortest)
{
  // check if partial solution has no chance of beating best so far
  if (num_partial >= *shortest)
    {
      return;
    }
  
  // check whether we have a solution
  if (sum_partial == target)
    {
      // check whether this solution is better than the best so far
      if (num_partial < *shortest)
	{
	  // remember this new best solution
	  for (int i = 0; i < num_partial; i++)
	    {
	      best[i] = partial[i];
	    }
	  *shortest = num_partial;
	}
    }
  else
    {
      // loop over all possible next pieces of partial solution
      int next = min;
      while (sum_partial + next * next <= target)
	{
	  // add the next piece into the solution
	  partial[num_partial] = next;
	  num_partial++;
	  sum_partial += next * next;

	  // recurse, passing
	  // 1) same information about what we're trying to achieve (target)
	  // 2) updated partial solution (partial, num_partial)
	  // 3) updated bookkeeping (sum_partial)
	  // 4) updated restrictions (fill out partial with squares >= next*next)
	  // 5) best solution so far (best, shortest)
	  find_sum(target, partial, num_partial, sum_partial, next, best, shortest);

	  // remove the piece we just added
	  sum_partial -= next * next;
	  num_partial--;

	  // go on to the next piece of partial solution
	  next++;
	}
    }
}