面经算法

有m个苹果，分给n个人，每人可以分到0-m个苹果，求有多少种分法？

做了一个回溯题，还记得一刷力扣的时候回溯真的一塌糊涂

在别人面经上看到这个题，想着做一下没做出来，重新记起回溯！！

import java.util.*;
import java.util.ArrayList;
import java.util.List;
class Solution {


    // 有m个苹果，分给n个人，每人可以分到0-m个苹果，求有多少种分法
    public static List<List<Integer>> getAllDistributions(int m, int n) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        backtrack(n, m, path, result);
        return result;
    }


    private static void backtrack(int remainPeople, int remainApples, List<Integer> path, List<List<Integer>> result) {
        // 终止条件
        if (remainPeople == 1) {
            // 就把剩余的苹果全部给最后一个人
            path.add(remainApples);
            result.add(new ArrayList<>(path));
            path.remove(path.size() - 1);
            return;
        }


        for (int i = 0; i <= remainApples; i++) {
            path.add(i);
            // 处理剩下的人
            backtrack(remainPeople - 1, remainApples - i, path, result);
            // 撤销选择：回溯，准备尝试其他分配
            path.remove(path.size() - 1);
        }
    }


}