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

采用回溯算法，在回溯的过程中，使用辅助变量记录总和，并利用组合的长度和总和的值进行剪枝，对满足要求的组合记录在ArrayList res中。

import java.util.*;
public class Solution {
    ArrayList> res = new ArrayList();
    ArrayList track = new ArrayList();
    int sum = 0;
    public int[][] combination (int k, int n) {
        backtrack(1,k,n);
        int[][] resArr = new int[res.size()][k];
        for(int i = 0;i<res.size();i++){
            for(int j = 0;j<k;j++){
                resArr[i][j] = res.get(i).get(j);
            }
        }
        return resArr;
    }
    private void backtrack(int start,int k, int n){
        if(track.size() == k && sum == n){
            res.add(new ArrayList(track));
        }
        if(track.size() > k || sum > n){
            return;
        }
        for(int i = start;i<10;i++){
            sum += i;
            track.add(i);
            backtrack(i+1,k,n);
            sum -= i;
            track.remove(track.size()-1);
        }
    }
}