题解 | #放苹果#

#include <atomic>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> result;
vector<int> path;
/*
int sum_up(vector<int>& vec)
{
    int sum=0;
    for(int num:vec){
        sum += num;
    }
    return sum;
}
*/
void backtracking(int m, int n, int plateIndex) //m为剩余苹果数， //n为盘子数
{
    for (int i = 0; i < n - 1; i++) {
        if (path[i] < path[i + 1]) return;
    }
    if (m == 0) {
        result.push_back(path);
        //cout << path[0] << path[1] << path[2] << endl;
        return;
    }

    for (int j = 0; j < m; j++) {
        path[plateIndex]++;
        backtracking(m - 1, n, plateIndex);
        j--;
        path[plateIndex]--;
        if (plateIndex < n - 1) {
            plateIndex++;
        }
        else break;
    }
}
int main() {
    int m, n;//m个同样的苹果，n个同样的盘子
    cin >> m >> n;
    path = vector<int>(n, 0);
    backtracking(m, n, 0);
    cout << result.size();
    return 0;
}
// 64 位输出请用 printf("%lld")