题解 | #四数之和#

nSum问题，递归模板

import java.util.*;
public class Solution {
    public ArrayList> fournumber (ArrayList nums, int target) {
        Collections.sort(nums);
        // System.out.println(nums);
        return nSumTarget(nums, 4, 0, target);
    }
    private ArrayList> nSumTarget(ArrayList nums,int n,int start,int target){
        int sz = nums.size();
        ArrayList> res = new ArrayList();
        if(n<2 || sz < n){
            return res;
        }
        if(n==2){
            int low = start,high = sz-1;
            while(low<high){
                int sum = nums.get(low)+nums.get(high);
                int left = nums.get(low),right = nums.get(high);
                if(sum<target){
                    while(low<high && nums.get(low) == left)
                        low++;
                }else if(sum > target){
                    while(low<high && nums.get(high) == right)
                        high--;
                }else{
                    res.add(new ArrayList(Arrays.asList(left,right)));
                    while(low<high && nums.get(low) == left)
                        low++;
                    while(low<high && nums.get(high) == right)
                        high--;
                }
            }
        }else{
            int i = start;
            while(i<sz){
                int now = nums.get(i);
                ArrayList> sub = nSumTarget(nums,n-1,i+1,target-nums.get(i));
                for(ArrayList s:sub){
                    s.add(now);
                    res.add(s);
                }
                while(i<sz && nums.get(i) == now)
                    i++;
            }
        }
        return res;
    }
}