#include<set>
#include<iostream>
#include<vector>
using namespace std;

int numSquares(int n) 
{//找出n所组成的最小的完全平方个数
	while(n%4==0) n/=4;
    if(n%8 == 7) return 4;
    for(int a = sqrt(n); a > 0; --a)
    {
        int b = sqrt(n-a*a);
        if(a*a+b*b == n) return !b? 1 : 2;
    }
    return 3;
}

set<int> get_data(int n){//获取每个完全平方数
	set<int> data;
	for(int i = 0; i<n; ++i){
		data.insert(i*i);
	}
	return data;
}
vector<int> get_out(set<int> data, int n, int m){//遍历，找出符合要求的完全平方数
		set<int> ::iterator it = data.begin();
		it = data.lower_bound(n);
		vector<int> out_o;
		int p = m;
		while(p--){
			--it;
			out_o.clear();
			set<int> ::iterator it1 = it;
			int a,s = 0,s1=0;
			while(it1!=data.begin()){
				a = *it1;
				s += a;
				if(s<n){
					out_o.push_back(a);
					--it1;
				}
				else if (s>n)
				{
					s -= a;
					--it1;
				}
				else{
					out_o.push_back(a);
					break;
				}
				if(out_o.size()>m)
					break;
			}
			int len = out_o.size();
			for(int i = 0; i<len; ++i)
				s1 += out_o[i];
			if(s1==n && len==m) break;
		}
		return out_o;
}

int main()
{
	int n;
	while(cin>>n){
		set<int> data;
		data = get_data(n);//集合中存放每个与下标对应的完全平方数
		int m = numSquares(n);//获取其和为n的最小的完全平方数的个数
		int s = 0;
		vector<int> out_o = get_out(data, n, m);//得到所求的完全平方数
		for(int i = out_o.size()-1; i>=0; --i){
			s += out_o[i];
		}
		if(s==n){
			for(int i = out_o.size()-1; i>=0; --i)
				cout<<out_o[i]<<" ";
		}
		else
			cout<<"NA";
		cout<<endl;
	}
	return 0;
}

我用了另外一种思路，这种方法既能保证从小到大又能是输出的个数最小，但是方法不是很简便，欢迎有更好思路的小伙伴可以留言评论。