N-sum问题通解

N-sum 问题还是比较典型的，这里进行一下小结。

首先描述一下 N-sum 问题：有一个数组 nums，要求从数组中选择 n 个数，使得这些数的和恰好为 target ，输出所有不重复的可行组合。

如果采用暴力解法，显然时间复杂度为 $O(N^n)$，这一般是不可取的。

下面是 N-sum 问题的LeeCode链接：

1. Two Sum

15. 3Sum

18. 4Sum

Two-Sum

先来解决Two-Sum问题，这是N-sum问题的基础。如果我们能把Two-Sum的时间复杂度降为 $O(N)$ ，然后就能把N-sum的时间复杂度降为 $O(N^{n-1})$ 了。

如果采用暴力解法，每次选择一个数时，都要遍历数组来选择另一个数，并判断和是否为 target，这样显然是低效的。当我们选择一个数 x 时，我们希望数组里有一个数为 target - x。为了快速判断数组里是否有某个数，可以用 HashSet。但是，这样存在问题，因为数组里可能有重复的数，当 x 等于 target - x 时，这种做法就错了。因此，正确的做法应该是用 HashMap，用来存储各个数还有多少可用。

双指针法

另一种解法是使用“双指针”，这种解法要求 nums 是有序的。例如，nums 为 [1, 2, 4, 7, 13, 16]，target 为 15。初始时，指针p、q位于两端：

如果p、q所指向的值之和大于 target，那么q往左移，这是因为q左侧的值比q所指的值小，所以q往左移能使得之和变小； 如果之和小于 target，那么p往右移，这是因为p右侧的值比p所指的值大，所以p往右移能使得之和变大； 如果之和等于 target，那么p往右移且q往左移（有点像夹挤），这个稍微有点难理解，这也是“双指针”法的思想精髓。首先，如果p往左移或q往右移，其实就回到了之前的状态；其次，如果只是p往右移，显然之和会大于 target，如果只是q往左移，显然之和会小于 target；于是乎，p往右移且q往左移。

然后就是考虑如何判断可行组合是否重复。由于数组是有序的，可行组合的加入也是有序的，因此，只需判断当前可行组合与最后一个已加入的可行组合是否重复即可。

代码

vector<vector<int>> twoSum(vector<int>& nums, int target, int st, int ed) {
    vector<vector<int> > res;
    while (st < ed) {
        if (nums[st] + nums[ed] == target) {
            if (res.empty() || res.back()[0] != nums[st]) {
                res.push_back(vector<int>{nums[st], nums[ed]});
            }
            ++st;
            --ed;
        } else if (nums[st] + nums[ed] > target) {
            --ed;
        } else {
            ++st;
        }
    }
    return res;
}

N-Sum

问题转化

对于 N-sum 问题，外面几层其实就是暴力遍历，只有最后两个数转为 Two-Sum 问题，使用双指针法求解。这种做法，其实就相当于把时间复杂度降了一阶。

例如，对于 3-Sum 问题，先从有序数组 nums 中取一个数（遍历），然后从该数右侧的数里再取两个数（Two-Sum）；对于 4-Sum 问题，先从有序数组 nums 中取两个数（遍历），然后从这两个数的右侧里再取两个数（Two-Sum）。可见，4-Sum 只是比 3-Sum 多了一层循环。为了控制循环层数，可以使用递归。

代码

vector<vector<int>> nSum(vector<int>& nums, int target, int st, int ed, int n) {
    vector<vector<int> > res;
    if (n == 2) {
        return twoSum(nums, target, st, ed);
    } else {
        for (int i=st; i<=ed; ++i) {
            int num = nums[i];
            if (res.empty() || res.back()[0] != num) {
                auto ret = nSum(nums, target-num, i+1, nums.size()-1, n-1);
                for (auto r : ret) {
                    vector<int> tmp;
                    tmp.push_back(num);
                    tmp.insert(tmp.end(), r.begin(), r.end());
                    res.push_back(tmp);
                }
            }
        }
        return res;
    }
}

“双指针”的想法还是比较巧妙的，如果没见过，还真的不容易想出来。所以，练习是有必要的，也需要进行归纳总结。