题解 | #加起来和为目标值的组合#

import java.util.*;


public class Solution {
    
    public class ComparaInteger implements Comparator<Integer> {
        @Override
        public int compare(Integer num1, Integer num2) {
            return num1 - num2;
        }
    }
    
    public ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public int tar;
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> combinationCount (int target, int[] nums) {
        // write code here
        ArrayList<Integer> arrayList = new ArrayList<>();
        tar = target;
        process(nums, arrayList, 0);
        return res;
    }
    
    // 递归函数
    public void process(int[] nums, ArrayList<Integer> arrayList, int total) {
        if (total == tar) {
            ArrayList<Integer> copyArrayList = new ArrayList<>();
            copyArrayList.addAll(arrayList);
            copyArrayList.sort(new ComparaInteger());
            if (!isContains(copyArrayList)) {
                res.add(copyArrayList);
            }
            return;
        }
        if (total > tar) { // 题目给定数组中的数都是正整数
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            arrayList.add(nums[i]);
            total += nums[i];
            process(nums, arrayList, total);
            // 别忘了回溯
            arrayList.remove(arrayList.size() - 1);
            total -= nums[i];
        }
        return;
    }
    
    // 判断一个二维数组是否包含一个一维数组
    public boolean isContains(ArrayList<Integer> arrayList) {
        boolean bool = false;
        for (ArrayList<Integer> tmp : res) {
            if (isEquals(tmp, arrayList)) {
                bool = true;
                break;
            }
        }
        return bool;
    }
    
    // 判断两个一维数组是否相等
    public boolean isEquals(ArrayList<Integer> arr1, ArrayList<Integer> arr2) {
        int len1 = arr1.size();
        int len2 = arr2.size();
        if (len1 != len2) {
            return false;
        }
        boolean bool = true;
        for (int i = 0; i < len1; i++) {
            if (arr1.get(i) != arr2.get(i)) {
                bool = false;
                break;
            }
        }
        return bool;
    }
}