Leetcode18: 四数之和

class Solution {
    //主函数调用
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = kSum(nums,target,4,0);
        return result;
    }
    //k数之和
    public List<List<Integer>> kSum(int[] nums, int target, int k, int start){
        List<List<Integer>> res = new ArrayList<>();
        if(start >= nums.length) return res;
        //先把两数之和写好
        if(k == 2){
            int n = nums.length, i = start, j = n - 1;
            while(i < j){
                if(nums[i] + nums[j] == target){
                    List<Integer> elem = new ArrayList<>();
                    elem.add(nums[i]);
                    elem.add(nums[j]);
                    res.add(elem);
                    while(i < j && nums[i] == nums[i+1]) ++i;
                    while(j > i && nums[j] == nums[j-1]) --j;
                    i++;
                    j--;
                }else if(nums[i]+ nums[j] < target) i++;
                else j--;
            }
            return res;
        }
        //之后就是递归的过程了
        if(k > 2){
            for(int i = start; i < nums.length - k + 1; i++){
                List<List<Integer>> temp = kSum(nums,target - nums[i], k-1,i+1);
                if(temp!=null){
                    for(List<Integer> l : temp){
                        l.add(0,nums[i]);
                    }
                    res.addAll(temp);
                }
                while(i < nums.length -1 && nums[i] == nums[i+1]) ++i;
            }
            return res;
        }
        return res;
    }
 }