对“编程小练习：拆分自然数”的解答

这是一篇从早期博客迁移来的 PDF 文章，主题是“拆分自然数”这道编程练习：给定 sum、min、max 和 n，输出所有把 sum 拆成 n 个正整数之和的方案，并要求每个数都落在 [min, max] 内，且忽略加法交换导致的重复排列。

长摘要：

文章先从最直接的暴力解法开始：枚举所有长度为 n、每个元素都在 [min, max] 中的序列，筛选出和为 sum 的结果，再通过排序和去重消除排列重复。这个做法效率很差，但实现简单、容易验证，可以用来生成小规模测试用例，帮助校验后续更复杂的算法。

随后，文章把题目形式化为一个递归问题：寻找非降序列 {a1, a2, ..., an}，满足总和为 sum，并且 min <= a1 <= a2 <= ... <= an <= max。通过分析输入约束，可以推导出第一个数 a1 的取值范围不仅要落在 [min, max]，还必须满足 a1 <= floor(sum / n) 和 a1 >= sum - max * (n - 1)，这样剩余问题才仍然有解。

最终解法是深度优先搜索：枚举合法的 a1，再递归求解 sum - a1、下界更新为 a1、数量减一的子问题。这个递归结构天然避免重复排列，也把剪枝条件建立在题目的数学约束上，而不是事后去重。