Backtracking - Combination Sum III

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.

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation: 1+2+4 = 7, and we need exactly 3 numbers.

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation: All triples from 1-9 summing to 9.

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.

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.