Сумма задача на жадный алгоритм!

Самое жадное - в смысле вычислительных ресурсов и времени - вычисление выглядит так:

long long count(long long n)
{
    return (((n+3)*n-9*(n%2))*n+72)/144;
}

См. Кнут, "Искусство программирования", т.4А, задача 7.2.1.4-31.

Сравнивал со своим решением

long long count(long n, long k = 4, long min = 1)
{
    if (n < min*k) return 0;
    if (k == 1) return 1;
    long long sum = 0;
    for(long long i = min; i <= n/k; ++i)
        sum += count(n-i,k-1,i);
    return sum;
}

Дает то же значение.

Если чисто N необходимо разложить на K слагаемых, то "разумный" алгоритм решения такой задачи будет основан на том факте, что для того, чтобы последовательность слагаемых была неубывающей, необходимо, чтобы первое слагаемое не превосходило [N / K] (более того, это еще и достаточное условие существования последовательности с таким первым слагаемым).

Отсюда получаем очевидный алгоритм: перебираем все возможные первые слагаемые S в диапазоне от 1 до [N / K], после чего применяем ту же самую логику для N - S и K - 1.

Будет ли такой алгоритм "жадным" в вашем определении - трудно сказать. Традиционная идея "жадного" алгоритма состоит в градиентной ("жадной") оптимизации некоей целевой функции. Я в данном случае не вижу никакой оптимизируемой целевой функции.

Задача больше математическая. Представим х как сумму единичек: х = 1 + 1 + 1 + ... + 1. Чтобы представить х как сумму 4 слагаемых, нужно разбить эту сумму единиц на 4 (как бы скобки расставить). Ну вот так, возможно, нагляднее даже будет: представим х как сумму счётных палочек: х = |.|.|.|....| Точки назовём "дырками", тогда для того, чтобы поделить это на 4 части, нужно "занять" 3 дырки. Это можно сделать С(3,х) (число сочетаний из Х по 4) способами. Но здесь только будут все варианты, поэтому результат надо еще поделить на 4!, чтобы отсортировать по возрастанию.

UPD: Делить не на 4!, а на меньшее число, нужно учитывать, что числа могут оказаться равны и тогда делить надо на меньшее число. Сходу так не придумал, а думать дольше сейчас нет времени, увы(