题意：给定一个整数数组和目标值target，返回所有可能的四数组合，要求满足四个数字各不相同且四数之和等于target。

18. 4Sum (opens new window)

四数之和，相比三数之和多了一个数，可以多加一层循环，但是如果题目改为五数之或者六数之和呢？所以我们需要找到一个通用的解法，三数之和其实可以看作四数之和更小规模的问题，可以用递归解决。

思路：

• 还是对数组排序。
• 定义kSum方法，接收4个参数，整数数组，目标值，开始位置，k。当k=2时，使用3Sum里的双指针方法。从开始位置开始遍历，剩下的k-1可以递归调用kSum(nums,target,start+1,k-1)。
• 因为要求数字各不相同，所以在kSum和2Sum里都要跳过相同数字。
• kSum可以剪枝的点，先计算出k个数的平均值avg=target/k。当当前位置的数字大于avg时说明k数之和肯定比target大，可以跳过，同理如果最后一个位置的值即最大数字比avg小说明k数之和肯定比target小，也可以跳过。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return kSum(nums, target, 0, 4);
    }

    public List<List<Integer>> kSum(int[] nums, long target, int start, int k) {
        List<List<Integer>> res = new ArrayList<>();

        // 边界情况跳过
        if (start == nums.length) {
            return res;
        }

        long avg = target/k;

        // 最小值超过平均数或者最大值小于平均数可以跳过
        if (nums[start] > avg || nums[nums.length - 1] < avg) {
            return res;
        }

        if (k == 2) {
            return twoSum(nums, target, start);
        }

        for (int i = start; i < nums.length; i++) {
            // 跳过相同的数字
            if (i == start || nums[i - 1] != nums[i]) {
                for (List<Integer> subset : kSum(nums, target - nums[i], i + 1, k - 1)) {
                    res.add(new ArrayList<>(Arrays.asList(nums[i])));
                    res.get(res.size() - 1).addAll(subset);
                }
            }
        }

        return res;
    }

    public List<List<Integer>> twoSum(int[] nums, long target, int start) {
        List<List<Integer>> res = new ArrayList<>();
        int left = start, right = nums.length - 1;

        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum < target || (left > start && nums[left] == nums[left - 1])) {
                left++;
                continue;
            }
            if (sum > target || (right < nums.length - 1 && nums[right] == nums[right + 1])) {
                right--;
                continue;
            }
            res.add(Arrays.asList(nums[left++], nums[right--]));
        }

        return res;
    }
}