LeetCode: 18. 4Sum

递归调用的例子，参考网上的实现https://discuss.leetcode.com/topic/46339/my-solution-generalized-for-ksums-in-java/5

class Solution {
       int len =0;
    public List<List<Integer>> fourSum(int[] nums, int target) {
        len = nums.length;
        Arrays.sort(nums);
        return kSum(nums, target, 4,0);
    }
    
    private ArrayList<List<Integer>> kSum(int[] nums,int target,int k,int index ){
        ArrayList<List<Integer>> list = new ArrayList<>();
        if(index>=nums.length){
            return list;
        }
        if(k==2){
            int left = index;
            int right = nums.length-1;
            while(left<right){
                if(nums[left]+nums[right]==target){
                        //list.add(Arrays.asList(nums[left],target-nums[left]));
                       List<Integer> temp = new ArrayList<>();
                    temp.add(nums[left]);
                    temp.add(nums[right]);
                       list.add(temp);
                    while(left<right&&nums[left]==nums[left+1]){
                        left++;
                    }
                    while(left<right&&nums[right]==nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }else if(nums[left]+nums[right]<target){
                    left++;
                }
                else if(nums[left]+nums[right]>target){
                    right--;
                }
                
            }    
        }else{
            for (int i = index; i < len - k + 1; i++) {
                //use current number to reduce ksum into k-1sum
                ArrayList<List<Integer>> temp = kSum(nums, target - nums[i], k-1, i+1);
                if(temp != null){
                    //add previous results
                    for (List<Integer> t : temp) {
                        t.add(0, nums[i]);
                    }
                    list.addAll(temp);
                }
                while (i < len-1 && nums[i] == nums[i+1]) {
                    //skip duplicated numbers
                    i++;
                }
            }
        }
        return list;
    }
}