自然数拆分

一个整数$n(n\ge 30)$可以有多种分划，分划的整数之和为$n$，在不区分分划出各整数的次序时，字典序递减输出$n$ 的各详细分划方案和分划总数。 例如$n=6$，程序输出为： 6 5 1 4 2 4 1 1 3 3 3 2 1 3 1 1 1 2 2 2 2 2 1 1 2 1 1 1 1 1 1 1 1 1 1 total = 11

# include <iostream> # include <vector> # include <algorithm> int a[105]; std::vector<std::vector<int>> vv; void save(int m) { std::vector<int> v; for (int i = m; i; i--) { v.push_back(a[i]); } vv.push_back(v); } void dfs(int k, int m) { for (int i = 1; i <= k / 2; i++) { if (i >= a[m - 1]) { a[m] = i; a[m + 1] = k - i; save(m + 1); dfs(k - i, m + 1); } } } int main() { int n; std::cin >> n; vv.push_back(std::vector<int>(1, n)); dfs(n, 1); std::sort(vv.begin(), vv.end(), std::greater<std::vector<int>>()); for (int i = 0; i < vv.size(); i++) { for (int j = 0; j < vv[i].size(); j++) { std::cout << vv[i][j] << " "; } std::cout << std::endl; } std::cout << "total = " << vv.size() << std::endl; return 0; }