拆分自然数：纯while实现 (Part 2 - 实现)

核心提示：在拆分自然数：纯while实现 (Part 1 - 思路) 这篇文章里面，我提供了解答Jeff《编程小练习：拆分自然数》问题的一种解答思路，拆分自然数：纯while实现 (Part 2 - 实现)，并且使用了两个例子来解释这种思路，不知道你是否已经成功利用这种思路解题了呢？首先，而不缓存下界（即itemMinInclu

在拆分自然数：纯while实现 (Part 1 - 思路) 这篇文章里面，我提供了解答Jeff《编程小练习：拆分自然数》问题的一种解答思路，并且使用了两个例子来解释这种思路，不知道你是否已经成功利用这种思路解题了呢？

首先，这道题的搜索域是什么？那就是[min, min, min, ..., min]到[max, max, max, ..., max]，或者是它的子集。就算你完全不懂算法，我相信你凭直觉也知道要在[min, min, min, ..., min]到[max, max, max, ..., max]之间搜索。因此，一个算法好不好，就看你能否有效缩小搜索域了。

在不缩小搜索域的情况下，你可以排列组合出搜索域内的所有可能性，逐一验证是否为所求解，这也就是Jeff的DoSimple示例所做的。接着，为了保持解的不重复性，你可能想到了有效解一定是一个不下降序列，因此对所有非不下降序列进行剪枝，这也就是Jeff的DoBetter示例所做的事情。然后，你需要把不下降序列中总和不等于 sum的情况给砍掉，这个剪枝就是最难的一个剪枝了，也就是DoBest所做的事情。

Jeff 在DoBest中的做法是，对于当前操作的第i位，求得itemMinInclusive与itemMaxInclusive，且 minInclusive <= itemMinInclusive <= itemMaxInclusive <= maxInclusive，其中[minInclusive, itemMinInclusive)和(itemMaxInclusive, maxInclusive]这两个区间的取值是无效的，只有[itemMinInclusive, itemMaxInclusive]区间的取值才是有效的。

dragonpig的展开采用了try方式的剪枝，虽然也把无效枝剪掉了，但在循环上还是要遍历到无效枝的首个无效节点，必须在上面try一下看返回false才剪掉，因此性能介于DoBetter与DoBest之间。徐少侠的展开进行了有效的剪枝，在时间复杂度上是与DoBest一致的，不过缓存数据占用空间为实际状态所需空间的3倍，这些空间其实是浪费掉的。我认为比较理想的做法是仅仅缓存sum值，而不缓存下界（即itemMinInclusive）与上界（即itemMaxInclusive），这样是保证性能的前提下最省空间的。至于为什么我说混存下界与上界没用，看一下我的写法就知道了：