// Four square decomposition
// Eric Conrad
// Descrption
//	This program displays all decompositions of an integer into
//	four squares using brute force.  The inner loop could be
//	optimized by using a better square root algorithm.

#include <stdlib.h>
#include <iostream.h>
#include <math.h>

class stack
	{	// No overflow checks are performed.
    private:
	int	top;
	int*	data;
    public:
	stack(int lgth) : top(0), data(0)
		{
		if(lgth>0)
			data = new int[lgth];
		}
	~stack()
		{
		if(data != 0)
			delete data;
		}
	void push(int item)
		{
		data[top++] = item;
		}
	int pop()
		{
		return data[--top];
		}
	int isEmpty()
		{
		return top==0;
		}
	int length()
		{
		return top;
		}
	void print();
	};

void stack::print()
	{
	cout << "[";
	if(top>0)
		{
		cout << data[0];
		for(int i=1; i<top; i++)
			cout << "," << data[i];
		}
	cout << "]\n";
	}

void process( stack&, int, int );

int main(int argc, char** argv)
	{
	if(argc != 3)
		{
		cout << "Usage: " << argv[0] << " integer1 integer2\n";
		cout << " where integer1 is the number of squares and\n";
		cout << "       integer2 is the number to decompose\n";
		return 1;
		}
	int r = atoi( argv[1] );
	int n = atol( argv[2] );
	stack S(r);
	process(S, r, n);
	return 0;
	}


void process( stack& S, int r, int n )
	{
		// trivial cases
	if(n<0)	return;

	if(n==0)
		{
		int i;
		for(i=0; i<r; i++)
			S.push(0);
		S.print();
		for(i=0; i<r; i++)
			(void) S.pop();
		return;
		}

	if(r==0) return;		// no solutions if n!=0 and r==0

	if(r==3 && n%8==7) return;	// no solutions
	if(r==2 && n%4==3) return;	// no solutions

	if(r==1)
		{
		if(n%4==3) return;

		int n5 = n%5;
		if(n5==2 || n5==3) return;

		int n7 = n%7;
		if(n7==3 || n7==5 || n7==6) return;
		}

		// end of trivial cases

	for(int s=-n; s<=n; s++)
		{
		S.push(s);
		process(S, r-1, n-s*s);
		(void) S.pop();
		}
	}