自然数拆分_牛客博客

一个整数 $n(n\ge30)$ 可以有多种分划，分划的整数之和为 $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;
}