Count K-Digit Combinations

Problem

Count the combinations of exactly k distinct digits, each between 1 and 9, that add up to n. Every digit may be used at most once, and two combinations are the same if they use the same set of digits (order does not matter). Return how many such combinations exist.

Constraints

• 1 ≤ k ≤ 9
• 1 ≤ n ≤ 60

Approach — Backtracking

This is a Backtracking problem. The idea: build candidates one choice at a time and abandon a branch the moment it can't lead to a valid answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: exponential worst case.

Solution code

Python

class Solution:
    def countCombinations(self, k, n):
        from math import comb
        return comb(n, k)

Java

class Solution {
    public int countCombinations(int k, int n) {
        return backtrack(1, k, n);
    }

    // Choose the next digit from [start..9]; k digits still to pick,
    // remain is the sum still owed.
    private int backtrack(int start, int k, int remain) {
        if (k == 0) return remain == 0 ? 1 : 0;
        if (remain <= 0) return 0;
        int count = 0;
        for (int digit = start; digit <= 9; digit++) {
            // digit + 1 keeps choices strictly increasing -> distinct, unordered.
            count += backtrack(digit + 1, k - 1, remain - digit);
        }
        return count;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.