Как работает этот рекурсивный алгоритм разложения на слагаемые?

Question

[nicknamecsharp]

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

#include <iostream>
#include <vector>

int ans = 0;

void f(int n, int maxx, std::vector<int> vv) {
    if (n == 0) {
        ans++;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (i <= maxx) {
            vv.push_back(i);
            f(n - i, i, vv);
            vv.pop_back();
        }
    }
}

int main() {
    int n;
    std::cin >> n;
    std::vector<int> v;
    f(n, n, v);
    std::cout << ans;
}

Comments

[Lynn «Кофеман»]

Попробуйте в районе ans++; вывести содержимое vv. Может тогда станет понятнее что происходит.

[pfemidi]

А я вот вообще ничего не понял, где результат работы этой функции, где это разбиение на слагаемые?

[Wataru]

pfemidi, в глобальной переменной ans будет их количество. Сами разбиения поадают в вектор vv, но нигде не используются и перезаписываются следующими. Этот вектор можно было бы выводить. Или вообще удалить. Сейчас он вообще не нужен.

Answer 1

[Wataru]

Функция генерирует все разбиения числа n на слагаемые не больше maxx. Ддя этого ыункуия перебирает, а какое же максимальное число будет в разбиении (цикл по i), берет это число и рекурсивно разбивает оставшуюся часть. Обратите внимание, в качестве maxx в рекурсии передается i. Ведь именно это было максимальное число в перебираемом разбиении. Значит следующее не может его превышать.

Вся эта сложность с максимальным числом сделана, что бы не перебирать перестановки слагаемых. Ведь 4=1+2+1 можно по идее получить тремя способами, меняя порядок. Генерируя слагаемые в не возрастающем прядке, мы избавляемся от таких дубликатов.