随笔档案

首先DFS有一个顺序性，这个顺序的好坏决定了剪枝的优劣。我们可以注意到此题要求求前N小的组合方案，所以应该基本上选择的都是每个序列中非常靠前的几个数。所以如果说从大的数开始搜索显然效率不好，所以应该把所有序列从小到大排序，这个是剪枝1)。再思考以后发现搜索到第i小的方案后找第i+1小的方案时，有很大可能是把某序列的数向后推了一个，并且这两个数一定是最接近的。所以如果说这种情况发生在搜索的最后一层效率会搞很多。所以我们应该把数与数之间相差最小的排在后面，所以我们可以把所有序列按方差从大到小排序，此为剪枝2)。还有一个剪枝非常明显，如果说此时我们已经搜到的前n小的和中的最大值，比我们现在搜索到位置的和要小，那么如果继续搜索下去不可能找到更小的值，所以直接回溯到上一层，此为简直3)。最后一个剪枝也比较关键，就是如何维护搜到的前n小的数，这时就需要利用堆了，此为剪枝4)。

综上所述，此题可以使用4个剪枝：

1)把所有序列从小到大排序

2)序列之间按方差从大到小排序

3)搜索到某一位置时的和已大于等于已有和的最大值，直接回溯

4)用堆维护前n小的和

1)、3)、4)的剪枝非常重要，用了这些剪枝就可以非常轻松并快速的解决此题。