【IT168技术文档】
转载自Jeff Zhao的博客
今天的题目如下：
给出sum、min、max和n四个正整数，请输出所有将sum拆分为n个正整数之和，其中每个正整数k都满足：min <= k <= max。这n个正整数之间可以重复，不过由于加法交换率的作用，1 + 2和2 + 1便算是重复的拆分了。
例如，sum = 5，n = 3，min = 1，max = 3，这时候满足条件的拆分方式只有两种：
1 + 1 + 3
1 + 2 + 2
这个练习和上次不同，我们假设所有的输入都是正整数。您无需对其进行合法性判断，只要专注于业务实现便是。您在看下面的内容之前，不如自己先简单尝试一下？老赵建议，您可以在这里阐述您的思路。至于代码，您可以在自己的博客上写一篇文章，然后再这里贴上链接，如果直接在这里贴代码的话，会使评论列表变得很长，影响阅读。点此展开
简单枚举
假设我们最后的结果存放在一个长度为n的int数组中。则解决这道题目最简单的方式，自然为数组的每个元素枚举min到max之间的所有值，并在得到一个枚举序列之后，判断它是否符合题目要求。如果是，则输出。代码如下：
{
int[] array = new int[n];
DoSimple(array, 0, min, max);
}
private static void DoSimple(int[] array, int n, int minInclusive, int maxInclusive)
{
if (n >= array.Length)
{
if (IsValidResult(array))
{
PrintResult(array);
}
return;
}
for (int i = minInclusive; i <= maxInclusive; i++)
{
array[n] = i;
DoSimple(array, n + 1, minInclusive, maxInclusive);
}
}
DoSimple的含义为，为array数组下标为n的位置中枚举minInvlusive到maxInclusive之间的所有值，并深入。如果array数组填充完毕，那么判断是否是一个正确的结果，并输出。在这个解法中IsValidResult方法的任务颇为繁重，它除了判断array中所有元素之和是否为sum以外，还要判断这个array所表示的拆分是否已经出现过了。例如在已经输出了1 + 1 + 3的情况下，就不能输出3 + 1 + 1。这些都必须在IsValidResult中进行判断，当然做到这点也并不困难。
不过这个做法的问题也是很明显的，就是重复太多。如果让我们进行“人力”拆分，我们肯定不会傻呆呆地为每个空格枚举从min到max之间的所有值。我们会知道，如果已经有了1 + 2，那么在出现2的时候，我们就不会再枚举1这个值。那么在编程时，我们又该如何进行限制呢？
原文地址：http://www.cnblogs.com/jeffreyzhao/archive/2009/06/21/1507847.html
