题解 | #科室素拓活动#

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    vector<vector<int>> ans;
    vector<int> tmp;
    
    void backtrack(int k, int n, int start) {
        if(k == 0) {
            if(n == 0) ans.push_back(tmp);
            return;
        }
        // 剪枝：剩余数字不足k个
        if(10 - start < k) return;
        
        for(int i = start; i <= 9; i++) {
            tmp.push_back(i);
            backtrack(k-1, n-i, i+1);
            tmp.pop_back();
        }
    }
    
public:
    vector<vector<int>> findCombinations(int k, int n) {
        backtrack(k, n, 1);
        return ans;
    }
};

int main() {
    int k, n;
    cin >> k >> n;
    
    Solution sol;
    auto result = sol.findCombinations(k, n);
    
    if(result.empty()) {
        cout << "None" << endl;
    } else {
        for(const auto& v : result) {
            for(int i = 0; i < k-1; i++) {
                cout << v[i] << " ";
            }
            cout << v[k-1] << endl;
        }
    }
    return 0;
}

import java.util.*;

public class Main {
    private static List<List<Integer>> ans = new ArrayList<>();
    private static List<Integer> tmp = new ArrayList<>();
    
    private static void backtrack(int k, int n, int start) {
        if(k == 0) {
            if(n == 0) ans.add(new ArrayList<>(tmp));
            return;
        }
        if(10 - start < k) return;
        
        for(int i = start; i <= 9; i++) {
            tmp.add(i);
            backtrack(k-1, n-i, i+1);
            tmp.remove(tmp.size()-1);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = sc.nextInt();
        
        backtrack(k, n, 1);
        
        if(ans.isEmpty()) {
            System.out.println("None");
        } else {
            for(List<Integer> combination : ans) {
                for(int i = 0; i < k-1; i++) {
                    System.out.print(combination.get(i) + " ");
                }
                System.out.println(combination.get(k-1));
            }
        }
    }
}

def backtrack(k: int, n: int, start: int, tmp: list, ans: list) -> None:
    if k == 0:
        if n == 0:
            ans.append(tmp[:])
        return
    
    # 剪枝：剩余数字不足k个
    if 10 - start < k:
        return
        
    for i in range(start, 10):
        tmp.append(i)
        backtrack(k-1, n-i, i+1, tmp, ans)
        tmp.pop()

def find_combinations(k: int, n: int) -> list:
    ans = []
    backtrack(k, n, 1, [], ans)
    return ans

k, n = map(int, input().split())
result = find_combinations(k, n)

if not result:
    print("None")
else:
    for combination in result:
        print(" ".join(map(str, combination)))