背景

两数之和是力扣上的第一个题，我至今记得当时做到的时候怀疑自己智商（毕竟大一没有学过什么是哈希表）。我们今天讨论一个简单的问题：

给定一系列数，以及一个目标值，请输出所有和为目标值的组合（不可重复）。

思路

看起来有一点吓人，我们从最简单的情况开始思考。

两数之和

最简单的做法是遍历+哈希，每次遇到一个数字，判断目标值-当前数字是否已经存在，如果存在，则两者可以组成一个组合。稍微修改一下可以去重。

如果数组有更强的性质——有序性（下文假设数组是单调递增的），那么这个问题可以通过一趟单纯的遍历完成：

使用两个指针分别指向数组的开始与结尾，任何时刻，如果两个指针指向的数字之和等于目标值，那么就是一个方案；如果小于，那么移动左侧指针，反之移动右侧指针。

怎么去重？当我们的左指针向右移动时，判断其是否与上一个位置相同即可。

怎么样，是不是很简单？我们来试试三数之和。三数之和，多了一个维度，我们可以枚举第一维，转化成一个两数之和问题。

怎么判重？与两数之和一样。

四数之和呢？同理，我们只需要枚举前两个维度。X数之和呢？我想你一定可以快速反应过来枚举前X-2个维度了，是不是很简单呢？

总结

大道至简，X数之和实际上可以退化成X-1数之和，依次递减……不过现实中很多问题没有这样的性质，有时候不要太固执于将一个问题转化成熟悉的问题，具体问题具体分析。