63 lines
1.7 KiB
C++
63 lines
1.7 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n = 5, m = 10;
|
||
//待处理的队列
|
||
queue<vector<int>> q;
|
||
//结果
|
||
vector<vector<int>> result;
|
||
|
||
//差距最大的情况是5+1+1+1
|
||
vector<int> v;
|
||
v.push_back(m - (n - 1));
|
||
for (int i = 0; i < n - 1; ++i) {
|
||
v.push_back(1);
|
||
}
|
||
//入队列，准备分解
|
||
q.push(v);
|
||
//同时加入第一组解
|
||
result.push_back(v);
|
||
|
||
//bfs
|
||
while (!q.empty()) {
|
||
//处理数组第一项的值
|
||
auto top = q.front();
|
||
int x = top[0];
|
||
//分别让第2位到第n-1位接收这个新产生出来的1
|
||
if (x > 2) { //不能无休止的下探，因为首位最小是2，再小就没意义了
|
||
for (int j = 1; j <= n - 1; ++j) {
|
||
//通过拷贝创建新的数组
|
||
vector<int> v2(top);
|
||
//修改数组的数据
|
||
v2[0] = x - 1; //首位
|
||
v2[j]++; //其它每一位都可以是加1
|
||
//加入队列
|
||
q.push(v2);
|
||
//加入结果
|
||
result.push_back(v2);
|
||
}
|
||
}
|
||
//弹出
|
||
q.pop();
|
||
}
|
||
//从大到小
|
||
for (int i = 0; i < result.size(); ++i) {
|
||
sort(result[i].begin(), result[i].end(), greater<int>());
|
||
}
|
||
//定义并初始化一个vector(去重)
|
||
set<vector<int>> s(result.begin(), result.end());
|
||
result.assign(s.begin(), s.end());
|
||
|
||
//输出
|
||
for (int i = 0; i < result.size(); ++i) {
|
||
for (int j = 0; j < result[0].size(); ++j) {
|
||
cout << result[i][j] << " ";
|
||
}
|
||
cout << endl;
|
||
}
|
||
|
||
return 0;
|
||
}
|