Combination Sum III

Share

Find all valid combinations of k numbers that sum up to n such that the following conditions are true: Only numbers 1 through 9 are used, and each number is used at most once. Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1
Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation: 1+2+4 = 7, and we need exactly 3 numbers.
Example 2
Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation: All triples from 1-9 summing to 9.

Solution Approach

Since only digits 1–9 are available and each digit can appear at most once, we iterate from a start digit up to 9. We track the count of numbers chosen and the remaining sum. Prune when the count exceeds k or the remaining sum goes negative.

  • Recurse with a start digit (1 initially), current count, and remaining sum.
  • Base case: if count equals k and remaining equals 0, record the combination.
  • Loop from start to 9; break early when digit exceeds remaining sum.
  • Add digit, recurse with digit+1, count+1, remaining-digit, then backtrack.
Java
import java.util.*;

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

    private void backtrack(int k, int remaining, int start,
                           List<Integer> current,
                           List<List<Integer>> result) {
        if (current.size() == k && remaining == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        if (current.size() == k || remaining <= 0) return;

        for (int digit = start; digit <= 9; digit++) {
            if (digit > remaining) break; // pruning
            current.add(digit);
            backtrack(k, remaining - digit, digit + 1, current, result);
            current.remove(current.size() - 1);
        }
    }
}
Complexity Analysis:

Time complexity: O(C(9, k)). We choose k numbers from 9 digits, at most 126 combinations.
Space complexity: O(k) for recursion depth and current combination.