题解 | #科室素拓活动#

import java.util.ArrayList;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k = in.nextInt(); // 组内元素个数
        int n = in.nextInt(); // 组内元素和
        List<List<Integer>> result = combinationSum3(k, n);
        if (result.isEmpty()) {
            System.out.println("None");
        } else {
            for (List<Integer> combination : result) {
                for (int num : combination) {
                    System.out.print(num + " ");
                }
                System.out.println();
            }
        }
    }

    public static List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(res, new ArrayList<>(), k, n, 1);
        return res;
    }

    // 回溯函数
    private static void backtrack(List<List<Integer>> res, List<Integer> tempList,
                                  int k, int remain, int start) {
        // 如果组合的元素数量超过k或剩余值小于0，直接返回
        if (tempList.size() > k || remain < 0) {
            return;
        }
        // 当tempList中正好有k个元素且剩余值为0时，找到符合要求的组合
        if (tempList.size() == k && remain == 0) {
            res.add(new ArrayList<>(tempList));
            return;
        }
        // 从start开始遍历，确保组合升序
        for (int i = start; i <= 9; i++) {
            tempList.add(i);
            backtrack(res, tempList, k, remain - i, i + 1);
            tempList.remove(tempList.size() - 1); // 回溯
        }
    }
}