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

Рекурсивный алгоритм разложения на слагаемые в C++ использует подход, основанный на принципе "разделяй и властвуй". Это означает, что задача разбивается на более простые подзадачи, решаемые рекурсивно, а затем их результаты комбинируются для получения конечного результата.

Давайте рассмотрим пример рекурсивного алгоритма разложения на слагаемые для заданного числа N.

#include <iostream>
#include <vector>

void разложение_на_слагаемые(int N, std::vector<int>& слагаемые) {
    // Базовый случай: если N равно 0, значит, разложение завершено
    if (N == 0) {
        // Выводим разложение на экран
        for (int i = 0; i < слагаемые.size(); i++) {
            std::cout << слагаемые[i] << " ";
        }
        std::cout << std::endl;
    }
    
    // Рекурсивный случай: перебираем все возможные слагаемые
    for (int i = 1; i <= N; i++) {
        // Добавляем текущее слагаемое в вектор слагаемых
        слагаемые.push_back(i);
        
        // Рекурсивно разлагаем оставшуюся сумму
        разложение_на_слагаемые(N - i, слагаемые);
        
        // Удаляем текущее слагаемое из вектора для перебора следующего слагаемого
        слагаемые.pop_back();
    }
}

int main() {
    int N;
    std::cout << "Введите число N: ";
    std::cin >> N;
    
    std::vector<int> слагаемые;
    разложение_на_слагаемые(N, слагаемые);
    
    return 0;
}

В этом алгоритме создается функция разложение_на_слагаемые, которая принимает входной параметр N - число, которое нужно разложить на слагаемые, и ссылку на вектор слагаемые, в котором будет храниться текущее разложение.

Алгоритм начинает с проверки базового случая, когда N равно 0, что означает завершение разложения. В этом случае он выводит текущее разложение на экран.

Если базовый случай не выполнен, алгоритм переходит к рекурсивному случаю. Он перебирает все возможные слагаемые от 1 до N и добавляет каждое слагаемое в вектор слагаемые. Затем алгоритм рекурсивно вызывает себя для разложения оставшейся части суммы N - i. После завершения рекурсивного вызова текущее слагаемое удаляется из вектора для последующего перебора следующего слагаемого.

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

Например, если мы введем число N равное 4, алгоритм выведет следующий результат:

Этот алгоритм работает за время O(2^N), так как для каждого числа от 1 до N существует два возможных варианта - использовать его в разложении или не использовать.