[LeetCode] 4Sum 解题报告

[题目] Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [-1, 0, 1, 2, -1, -4], and target = 0.

A solution set is: [  [-1, 0, 0, 1],  [-2, -1, 1, 2],  [-2, 0, 0, 2] ]

[中文翻译] 给定n个整数的数组S，在S中是否存在四个元素a，b，c 和d，使得a + b + c + d =target？找到数组中所有和为target的不同的四元组。 注意：解决方案集不能包含重复的四元组。

例如， 给定数组S = [-1, 0, 1, 2, -1, -4]，以及target = 0。

解集为： [  [-1, 0, 0, 1],  [-2, -1, 1, 2],  [-2, 0, 0, 2] ]

[解题思路] 四元组的问题可以归约到三元组的问题，思路参考[LeetCode] 3Sum 解题报告 和 [LeetCode] 3Sum Closest 解题报告 。 另外，关于K Sum问题，有一个挺好的Summary，参考Summary for LeetCode 2Sum, 3Sum, 4Sum, K Sum ，这篇博客还给出了比O(n³)更优的解法（使用hash）。

这次的代码做了一些调整，相对于上一次的3Sum Closest更简洁，细细读一遍应该能看明白。 /*再补两篇博客，以后写代码尽量给出注释来>_<*/

[C++代码]