python/TangDou/XiTi/1122CG05.cpp

#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;
}