[Java算法] - n 数之和解题模板（nSum）

注意：

1. 输入数组必须使用 Arrays.sort排序！
2. 返回List结果不包含重复值；
3. 核心思路是以2Sum为基准，通过递归重复计算。

代码：

   
    public List> nSum(int[] nums, int target, int n, int startIndex) {
        // 返回结果
        List> res = new ArrayList>();
        // base case
        if (startIndex > nums.length - 1) {
            return res;
        }
        if (n == 2) {
            int left = startIndex, right = nums.length - 1;
            while (left < right) {
                int twoSumTarget = nums[left] + nums[right];
                // 用于消重的基准值
                int baseLeft = nums[left], baseRight = nums[right];
                if (twoSumTarget == target) {
                    List tmp = new ArrayList<>();
                    tmp.add(nums[left]);
                    tmp.add(nums[right]);
                    res.add(tmp);
                    while (left < right && nums[left] == baseLeft) left++;  // 消重
                    while (left < right && nums[right] == baseRight) right--;  // 消重
                } else if (twoSumTarget > target) {
                    right--;
                    while (left < right && nums[right] == baseRight) right--;  // 消重
                } else if (twoSumTarget < target) {
                    left++;
                    while (left < right && nums[left] == baseLeft) left++;  // 消重
                }
            }
        } else {
            // n>2的时候调用递归
            for (int i = startIndex; i < nums.length; i++) {
                List> nRes = nSum(nums, target - nums[i], n - 1, i + 1);
                for (List list : nRes) {
                    list.add(nums[i]);
                    res.add(list);
                }
                while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;  // 消重
            }
        }
        return res;
    }