思路:

  1. 找到 初始数组 中 任意两个数相加 的结果，用一个 ArrayList 存放。(踩过的坑: 千万别用 HashSet 存放，有问题，不要去重!)
  2. 在 上述中，我们找到了任意两数两两相加的 结果，接下来我们要找到，对于该结果，有哪些组合。(例如: 对于 4 来说，它可以由 2 和 2 组成，也可以由 1 和 3 组成。) 我们的目的就是要找到 所有的组合，并且 去重! 在这里，我们使用 HashMap<Integer,HashSet<ArrayList>> 进行存储。其中，Key 指的是 该结果，Value 指的是 组成该结果的所有组合(含去重)。
  3. 同时，我们还要找到 初始数组中，每一个数字出现的次数，用一个 HashMap 进行存储。(后面有用!)
  4. 上述 3个 步骤看似复杂，其实都是在同一个 双层循环 中进行处理的，所以时间复杂度为 O(n^2)。
  5. 此时，我们已经获取到了 最重要的 3 个数据结构，此时，本题就可以退化成了，求两数相加。只不过，这里的 两数，本身也是由 两个数 组成的。

注意点:

1）、初始时，需要对初始数组进行排序。这一步骤的目的是为了在上述的 2步骤(找组合) 的过程中，确保每个组合有序，方便 HashSet 进行去重。

2）、在进行 5步骤(两数相加，求最终的结果) 过程中，我们要对 当前的一个组合(组合内有 4 个数) 进行合法性验证，这时，我们就用到了 3步骤 找到的 HashMap 结构了。为什么要这么做? 因为虽然在 5步骤 中，我们最终将整个题退化成了两数相加，但事实上，某一个数，它可能只在 原始数组 中出现了 1 次，但是它却在组合中出现了多次!(举个例子: 比如说，数字 1 只出现了 1 次，数字 1 可以组成 数字 3，(1 + 2 = 3) 和 数字 6，(1 + 5 = 6)，最终目标是要找到数字 9 的所有组合，那我们理所当然的认为，3 + 6 = 9，所以就找到了一个 [1,1,2,5]的组合了。但是，别忘了，数字 1 只有 1 个!)

import java.util.*;


public class Solution {
    public static class ComparaInteger implements Comparator<Integer> {
        @Override
        public int compare(Integer num1, Integer num2) {
            return num1 - num2;
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型ArrayList 
     * @param target int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> fournumber (ArrayList<Integer> nums, int target) {
        // write code here
        nums.sort(new ComparaInteger()); // 排序
        HashMap<Integer, Integer> eachNumberOccurrences = new HashMap<>();
        ArrayList<Integer> TwoSum = new ArrayList<>();
        HashMap<Integer, HashSet<ArrayList<Integer>>> twoSumGroups = new HashMap<>();
        for (int i = 0; i < nums.size() - 1; i++) {
            int occurrences = eachNumberOccurrences.getOrDefault(nums.get(i), 0);
            occurrences++;
            eachNumberOccurrences.put(nums.get(i), occurrences);
            for (int j = i + 1; j < nums.size(); j++) {
                TwoSum.add(nums.get(i) + nums.get(j));
                HashSet<ArrayList<Integer>> newSet = new HashSet<>();
                HashSet<ArrayList<Integer>> previousSet = twoSumGroups.getOrDefault(nums.get(i) + nums.get(j), newSet);
                ArrayList<Integer> currentArr = new ArrayList<>();
                currentArr.add(nums.get(i));
                currentArr.add(nums.get(j));
                previousSet.add(currentArr);
                twoSumGroups.put(nums.get(i) + nums.get(j), previousSet);
            }
        }
        int occurrences = eachNumberOccurrences.getOrDefault(nums.get(nums.size() - 1), 0);
        occurrences++;
        eachNumberOccurrences.put(nums.get(nums.size() - 1), occurrences);
        HashSet<ArrayList<Integer>> ans = new HashSet<>();
        HashMap<Integer, Integer> twoSumOccurrences = new HashMap<>();
        for (int i = 0; i < TwoSum.size(); i++) {
            occurrences = twoSumOccurrences.getOrDefault(target - TwoSum.get(i), -1);
            if (occurrences != -1) {
                HashSet<ArrayList<Integer>> groups1 = twoSumGroups.get(TwoSum.get(i));
                HashSet<ArrayList<Integer>> groups2 = twoSumGroups.get(target - TwoSum.get(i));
                for (ArrayList<Integer> tmpArr1 : groups1) {
                    for (ArrayList<Integer> tmpArr2 : groups2) {
                        ArrayList<Integer> copyArr = new ArrayList<>(tmpArr1);
                        copyArr.addAll(tmpArr2);
                        if (isValid(copyArr, eachNumberOccurrences)) {
                            copyArr.sort(new ComparaInteger());
                            ans.add(copyArr);
                        }
                    }
                }
            }
            twoSumOccurrences.put(TwoSum.get(i), 1);
        }
        ArrayList<ArrayList<Integer>> res = new ArrayList(ans);
        return res;
    }
    public static boolean isValid(ArrayList<Integer> nums, HashMap<Integer, Integer> eachNumberOccurrences) {
        HashMap<Integer, Integer> copyHash = new HashMap<>(eachNumberOccurrences);
        for (int num : nums) {
            int acc = copyHash.get(num);
            acc--;
            if (acc < 0) {
                return false;
            }
            copyHash.put(num, acc);
        }
        return true;
    }
}