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

import java.util.*;


public class Solution {
    
    public ArrayList<ArrayList<Integer>> res = new ArrayList<>(); // 定义一个二维数组，用于存放最终的返回结果
    public int[] arr = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9}; // 根据题目要求，组合中只能有 1~9 的正整数
    public int K; // 一共有 k 个数
    public int N; // 相加之和是 n
    // 自定义一个比较器，实现 ArrayList<Integer> 的排序
    public class ComparaInteger implements Comparator<Integer> {
        @Override
        public int compare(Integer num1, Integer num2) {
            return num1 - num2;
        }
    }
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param k int整型 
     * @param n int整型 
     * @return int整型二维数组
     */
    public int[][] combination (int k, int n) {
        // write code here
        // 初始化变量
        K = k;
        N = n;
        
        ArrayList<Integer> cur = new ArrayList<>();
        process(0, cur, 0);
        
        // 返回最终结果前，还要对结果集进行类型转换
        int[][] ra = new int[res.size()][K];
        for (int i = 0; i < res.size(); i++) {
            for (int j = 0; j < K; j++) {
                ra[i][j] = res.get(i).get(j);
            }
        }
        return ra;
    }
    
    // start    当前遍历到的 arr 数组的位置
    // cur      当前的一个组合
    // num      当前的组合中的和为多少
    public void process(int start, ArrayList<Integer> cur, int num) {
        if (cur.size() == K) { // 当组合中的数的个数已经达到了 k，就不能再往里面放数字了
            if (num == N) { // 如果当前组合的和恰好为 n，那么我们找到了一个组合
                ArrayList<Integer> tmpArray = new ArrayList<>();
                tmpArray.addAll(cur);
                tmpArray.sort(new ComparaInteger());
                res.add(tmpArray);
            }
            return;
        }
        if (start >= arr.length) {
            return;
        }
        for (int i = start; i < arr.length; i++) {
            int tmp = arr[i];
            num += tmp;
            cur.add(tmp);
            process(i + 1, cur, num);
            // 别忘了进行回溯
            num -= tmp;
            cur.remove(cur.size() - 1);
        }
        return;
    }
}