暴搜所有组合应该怎么剪枝? 求思路

Question

题目简述

要求输出n个正整数，他们的和为s, 每个元素值的范围在[1,m]之内。求输出所有可能的组合结果。

输入: n = 2, m = 6, s = 10，下面简述为(n, m, s), 即（2，6，10）

输出:
(4,6)
(5,5)

注意:
(6,4)属于重复的结果

边界约束:
1 <= n <= 100
1 <= m <= 1e9
1 <= s <= 1e5

问题

我用dfs暴力搜索 + 剪枝，但是还是通过不过用例。
(100, 100, 10000)
(3, 1e5, 20)

Answer 1

1.由于多少个元素不确定，肯定是要递归的，写死循环不可行
2.不用剪枝，递归的时候传递初始值内层与外层相等即可，这样4只能和4,5,6去加，5只能和5,6,7加，6只能和6,7,8加，不能输入的更小
3.暴力搜索容易超时，你应该判断如果不是最后一层递归，相加的结果已经大于给定的数，就结束本次循环，不要继续了（只影响当前的层，返回上一层之后继续外层循环）
4.如果是最后一层，不要再循环了，直接用给定的数减去前n-1项的和就是最后一项，为防止最后一项小于倒数第2项，这个条件可以在前面3的时候就过滤掉，不要继续循环了