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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param k int整型 
     * @param n int整型 
     * @return int整型二维数组
     */
    ArrayList<ArrayList<Integer>> results = new ArrayList<>();
    int[] candicates = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
    public int[][] combination (int k, int n) {
        // write code here
        dfs(n,k,0,new ArrayList<Integer>());
        int[][] res = new int[results.size()][];
        for(int i = 0; i < res.length; i++){
            res[i] = new int[results.get(i).size()];
            for(int j = 0; j < results.get(i).size(); j++){
                res[i][j] = results.get(i).get(j);
            }
        }
        return res;
    }

    private void dfs(int rest,int k,int idx,ArrayList<Integer> path){
        if(rest < 0){
            return;     // 凑过头了，本次组合无效
        }
        if(path.size() == k){
            // 够k个数且凑足目标值了就添加答案
            if(rest == 0){
                results.add(new ArrayList<>(path));
            }
        }else{
            for(int i = idx; i < candicates.length; i++){
                path.add(candicates[i]);
                dfs(rest - candicates[i], k, i + 1, path);
                path.remove(path.size() - 1);
            }
        }
    }
}