2Sum 3Sum 4Sum 问题

https://mp.weixin.qq.com/s/fSyJVvggxHq28a0SdmZm6Q

NSum Template

 public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return nSumHelper(4, 0, target, nums);
    }
    
    /* 注意：调用这个函数之前一定要先给 nums 排序 */
    // n is n sum
    public List<List<Integer>> nSumHelper(int n, int start, int target, int[] nums)
    {
        int size = nums.length;
        List<List<Integer>> res = new ArrayList<>();

        if(n < 2 || size < n) return res;
        if(n == 2)
        {
            int startIndex = start;
            int endIndex = size-1;

            while(startIndex < endIndex)
            {
                int sum = nums[startIndex] + nums[endIndex];
                int left = nums[startIndex];
                int right = nums[endIndex];

                if(sum > target)
                {
                    while(startIndex < endIndex && nums[endIndex] == right)  endIndex--;
                }
                else if (sum < target)
                {
                    while(startIndex < endIndex && nums[startIndex] == left) startIndex++;
                }
                else
                {
                    List<Integer> element = new ArrayList<Integer>();
                    element.add(left);
                    element.add(right);
                    res.add(element);
                    while(startIndex < endIndex && nums[startIndex] == left) startIndex++;
                    while(startIndex < endIndex && nums[endIndex] == right) endIndex--;
                }
            }
        }
        else
        {
            //注意这里是从 i = start
            // n > 2 时，递归计算 (n-1)Sum 的结果
            for(int i = start; i< size; i++)
            {
                List<List<Integer>> subRes= nSumHelper(n-1, i+1, target-nums[i], nums);
                for(List<Integer> tuple: subRes)
                {
                    tuple.add(nums[i]);
                    res.add(tuple);
                }

                while(i < size-1 && nums[i] == nums[i+1]) i++;
            }
        }
        return res;
    }