# LC18 - 4Sum
# 双指针

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

    private List<List<Integer>> kSum(int[] nums, int target, int k, int start) {
        
        int length = nums.length;
        if (k < 2 || length < k) {
            return new ArrayList<>();
        }

        if (k == 2) {
            return twoSum(nums, target, start);
        }
        
        List<List<Integer>> result = new ArrayList<>();
        for (int i = start; i < length; i++) {
            List<List<Integer>> subResult = kSum(nums, target - nums[i], k - 1, i + 1);
            for (List<Integer> temp: subResult) {
                temp.add(nums[i]);
                result.add(temp);
            }
            while (i < length - 1 && nums[i] == nums[i + 1]) {
                i++;
            }
        }
        
        return result;
    }

    private List<List<Integer>> twoSum(int[] nums, int target, int start) {
        List<List<Integer>> result = new ArrayList<>();

        int leftIdx = start;
        int rightIdx = nums.length - 1;

        while (leftIdx < rightIdx) {

            int leftVal = nums[leftIdx], rightVal = nums[rightIdx];
            int sum = leftVal + rightVal;
            int middleIdx = leftIdx + (rightIdx - leftIdx) / 2;
            int middleVal = nums[middleIdx];

            if (sum > target) { // shrink right bound
                if (leftVal + middleVal > target) {
                    rightIdx = middleIdx;
                    rightVal = middleVal;
                }
                while (leftIdx < rightIdx && rightVal == nums[rightIdx]) {
                    rightIdx--;
                }
            } else if (sum < target) { // shrink left bound
                if (middleVal + rightVal < target) {
                    leftIdx = middleIdx;
                    leftVal = middleVal;
                }
                while (leftIdx < rightIdx && leftVal == nums[leftIdx]) {
                    leftIdx++;
                }
            } else {
                List<Integer> temp = new ArrayList<>();
                temp.add(leftVal);
                temp.add(rightVal);
                result.add(temp);
                while (leftIdx < rightIdx && rightVal == nums[rightIdx]) {
                    rightIdx--;
                }
                while (leftIdx < rightIdx && leftVal == nums[leftIdx]) {
                    leftIdx++;
                }
            }
        }

        return result;
    }
}