Разбиение на невозрастающие слагаемые, лексикографический порядок c++

Question

Разбиение на невозрастающие слагаемые, лексикографический порядок c++

Камиль галимханов Ученик (125), на голосовании 3 месяца назад

Дано натуральное число N. Рассмотрим его разбиение на натуральные слагаемые. Два разбиения, отличающихся только порядком слагаемых, будем считать за одно, поэтому можно считать, что слагаемые в разбиении упорядочены по невозрастанию.
Формат ввода
Задано единственное число N. (N ≤ 40)

Формат вывода
Необходимо вывести все разбиения числа N на натуральные слагаемые в лексикографическом порядке.

Дополнен 4 месяца назад

также если вам не сложно можете написать код для обратного лексикографического порядка

Answer 1

 #include  
#include  
 
using namespace std; 
 
void generate_partitions(int n, int max_val, vector& partition) { 
    if (n == 0) { 
        for (int i = 0; i < partition.size(); ++i) { 
            cout << partition[i]; 
            if (i != partition.size() - 1) { 
                cout << " "; 
            } 
        } 
        cout << endl; 
        return; 
    } 
 
    for (int i = max_val; i >= 1; --i) { 
        if (n >= i) { 
            partition.push_back(i); 
            generate_partitions(n - i, i, partition); 
            partition.pop_back(); 
        } 
    } 
} 
 
int main() { 
    int N; 
    cin >> N; 
 
    vector partition; 
    generate_partitions(N, N, partition); 
 
    return 0; 
}