class Solution {

    Map<Integer, Map<String, List<Integer>>> pairs = new HashMap<>();

    Map<String, List<Integer>> results = new HashMap<>();

    Map<Integer, Integer> numbers = new HashMap<>();

    public List<List<Integer>> fourSum(int[] nums, int target) {

        for(int n : nums){
            if( numbers.get(n) == null){
                numbers.put(n, 1);
            }
            else{
                numbers.put(n, numbers.get(n)+1);
            }
        }

        for(int x : numbers.keySet()){
            for(int y : numbers.keySet()){
                if(x==y){
                    if( numbers.get(x) == 1){
                        continue;
                    }
                }

                 List<Integer> r = new ArrayList<>();

                 r.add(x);
                 r.add(y);
                 Collections.sort(r);

                 int sum = x + y;

                if(pairs.get(sum) == null){
                    Map<String, List<Integer>> p = new HashMap<>();
                    p.put(toKey(r),r);
                    pairs.put(sum, p);
                }
                else{
                    Map<String, List<Integer>> p= pairs.get(sum);
                    p.put(toKey(r),r );
                    pairs.put(sum, p);
                }

            }
        }

        for(int x : numbers.keySet()){
            for(int y : numbers.keySet()){
                if(x==y){
                    if( numbers.get(x) == 1){
                        continue;
                    }
                }

                int needed = target - x - y;

                if( pairs.get(needed) != null){
                    Map<String, List<Integer>> p = pairs.get(needed);

                    for( String k: p.keySet()){
                        List<Integer> pair = p.get(k);
                        int a = pair.get(0);
                        int b = pair.get(1);

                        Map<Integer, Integer> counts = new HashMap<>();

                        countNum(x,counts);
                        countNum(y,counts);
                        countNum(a,counts);
                        countNum(b,counts);

                        boolean skip = false;

                        for(int n : counts.keySet()){


                            if(numbers.get(n) < counts.get(n)){
                                skip =true;
                                break;
                            }
                        }

                        if(skip){
                            continue;
                        }

                        List<Integer> r = new ArrayList<>();

                         r.add(x);
                         r.add(y);
                        r.add(a);
                         r.add(b);
                         Collections.sort(r);

                        results.put(toKey(r), r);

                    }
                }
            }
        }

        List<List<Integer>> ret = new ArrayList<>();

        for(String s : results.keySet()){
            ret.add(results.get(s));
        }

        return ret;
    }


    public void countNum(int num, Map<Integer, Integer> map){
        if(map.get(num) ==null){
            map.put(num,1);
        }
        else{
            map.put(num, map.get(num)+1);
        }
    }

    public String toKey(List<Integer> nums){

        String ret = "";

        for(int x : nums){
            ret += "+"+x;
        }
        return ret;
    }

}