Получить все представления числа суммой квадратов целых положительных чисел

#include "stdafx.h"
 
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <cctype>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>
#include <locale>
 
#include <iterator>
 
using namespace std;
 
 
set<multiset<int, less<int>>, less<multiset<int, less<int>>>> result;
 
 
int getInput();
void Task(vector<int> const &, multiset<int, less<int>> const &, int);
void printmSet(multiset<int, less<int>> const &);
 
int _tmain(int argc, _TCHAR* argv[])
{
    locale::global(locale("Russian_Russia.1251"));
    cin.imbue(locale("Russian_Russia.866"));
    cout.imbue(locale("Russian_Russia.1251"));
 
 
    int const N(getInput());
    multiset<int, less<int>> initialMset;
    vector<int> initialVector;
 
    vector<int>::size_type max_size = static_cast<vector<int>::size_type>(floor(sqrt(static_cast<double>(N))));
    for (vector<int>::size_type i = 1; i <= max_size; ++i)
        initialVector.push_back(i * i);
 
    Task(initialVector, initialMset, N);
 
    cout << endl << endl;
    cout << "Список всех разложений" << endl;
    cout << "(с точностью до порядка слагаемых)" << endl;
    cout << "на квадраты данного числа" << endl << endl;
    set<multiset<int, less<int>>, less<multiset<int, less<int>>>>::const_iterator iter;
    for (iter = result.begin(); iter != result.end(); iter++)
        printmSet(*iter);
 
 
 
 
    return 0;
}
 
int getInput()
{
    int n;
    string s;
 
    cout << "Введите целое положительное число, состоящее не более чем из 9 цифр: ";
    getline(cin, s);
    while (true)
    {
        if (s.length() == 0)
        {
            cout << "Число не введено, попробуйте еще раз...";
            getline(cin, s);
            continue;
        }
        else if (s.length() > 9)
        {
            cout << "Слишком длинное, попробуйте еще раз...";
            getline(cin, s);
            continue;
        }
        else
        {
            bool badInput = false;
            for (int i = 0; i < s.length(); ++i)
                if (!isdigit(s[i]))
                {
                    badInput = true;
                    break;
                }
            if (badInput == true)
            {
                cout << "Ошибочный ввод, попробуйте еще раз...";
                getline(cin, s);
                continue;
            }
        }
        n = atoi(s.c_str());
        if (n == 0)
        {
            cout << "Неинтересно, тривильный случай, попробуйте еще раз... ";
            getline(cin, s);
            continue;
        }
        else
            break;
    }
    return n;
}
 
void Task(vector<int> const & curvect, multiset<int, less<int>> const & curmset, int tailnum)
{
    vector<int> workvect(curvect);
    multiset<int, less<int>> workmset(curmset);
 
    switch (tailnum)
    {
        case 0:
            result.insert(workmset);
            return;
        case 1:
            workmset.insert(1);
            result.insert(workmset);
            return;
        case 2:
            workmset.insert(1);
            workmset.insert(1);
            result.insert(workmset);
            return;
        case 3:
            workmset.insert(1);
            workmset.insert(1);
            workmset.insert(1);
            result.insert(workmset);
            return;
        default:
            for (vector<int>::const_reverse_iterator riter = workvect.rbegin(); riter != workvect.rend(); ++riter)
            {
                int newtail = tailnum - *riter;
                int max_size = static_cast<vector<int>::size_type>(floor(sqrt(static_cast<double>(newtail))));
                vector<int> newvect;
                for (vector<int>::size_type i = 1; i <= max_size; ++i)
                    newvect.push_back(i * i);
                multiset<int, less<int>>::iterator iter = workmset.insert(*riter);
                Task(newvect, workmset, newtail);
                workmset.erase(iter);
            }
    }
}
 
void printmSet(multiset<int, less<int>> const & mset)
{
    static int i(1);
    ostream_iterator<int> output (cout, " + ");
    cout << setw(5) << i++ << "." << '\t';
    copy(mset.begin(), mset.end(), output);
    cout << '\b'  << '\b' << " " << endl;
}

#include "iostream.h"
#include "math.h"
#include <conio.h>
#include <stdio.h>
int main(int argc, char* argv[])
{
int k,i,j,q,n,N,Z;
int *A,*S;
 
cout << "N=";
cin >> N;
 
n=(int)sqrt(N)+1;
 
S=new int[n];
 
for (i=0; i< n; i++) S[i]=i*i;
 
for (k=2; k<=n; k++)
{
 
A=new int[k];
 
for (i=0; i<k; i++) A[i]=i;
 
while (1)
{
 
Z=0;
for (i=0; i<k; i++)
{
j=A[i];
Z=Z+S[j];
}
if (Z == N)
{
q=0;
for (i=0; i<k; i++)
if (S[A[i]]==0)
{
q=-1;
break;
}
if (q == 0)
{
for (i=0; i<k; i++)
cout << S[A[i]] << " ";
cout << endl;
}
}
 
q=0;
 
for (j=k-1; j>=0; j--)
if (A[j] != (n-k+j))
{
q=-1;
A[j]++;
for (i=j+1; i<k; i++) A[i]=A[i-1]+1;
break;
}
if (q == 0){
printf("Nevozmozhno");
getch()  ;
return 0;
}
}
}
 }

#include <iostream>
#include <vector>
 
int n, cnt = 0;
std::vector <int> vec, res;
 
void rec(int remain, int idx) { // remain - осталось набрать
    if (!remain) {
        for (int i = 0; i < idx; ++i)
            std::cout << res[i] << " ";
        std::cout << std::endl;
        ++cnt;
    } else {
        for (int i = 0; i < vec.size(); ++i) {
            if (remain - vec[i] >= 0) {
                if ((idx && res[idx - 1] < vec[i]) || (!idx)) {
                    res[idx] = vec[i];
                    rec(remain - vec[i], idx + 1);
                }
            }
        }
    }
}
 
int main() {
    std::cin >> n;
    for (int i = 2; i * i <= n; ++i)
        vec.push_back(i * i);
 
    res.resize(n);
    rec(n, 0);
    if (!cnt)
        std::cout << "not";
    return 0;
}