172. Combination Sum III

Build combinations by trying digits in increasing order, each used at most once. Carry a start index so digits never repeat and combinations aren't regenerated in different orders. Prune as soon as a digit exceeds the remaining sum.

Search, but pruned and ordered

We want every set of k distinct digits from 1..9 that adds to n. Do a depth-first search that always picks digits in increasing order — that single rule guarantees each combination is generated exactly once (never [1,2,4] and [2,1,4]).

The recursion

Carry three things: the next digit to consider (start), how many digits are still needed (k), and the remaining sum (remaining).

if k == 0 and remaining == 0: record the current path   # exactly k digits, exact sum
if k == 0 or remaining <= 0:   return                    # dead end
for d in start..9:
    if d > remaining: break     # digits only grow -> prune the rest
    choose d; recurse(d+1, k-1, remaining-d); un-choose d

Because digits are ascending and positive, once d > remaining every later digit also overshoots, so we can break the whole loop.

Worked example

k = 3, n = 9.

• Start d=1: need 2 more summing to 8 from {2..9}.
  • d=2: need 1 more summing to 6 → digit 6 → [1,2,6] ✓
  • d=3: need 1 more summing to 5 → digit 5 → [1,3,5] ✓
  • d=4: need 1 more summing to 4, but must be > 4 → none.
• Start d=2: need 2 more summing to 7 from {3..9}.
  • d=3: 1 more summing to 4 → digit 4 → [2,3,4] ✓
• Start d=3: need 2 more summing to 6 from {4..9} → smallest pair 4+5=9 > 6 → none.

Result: [[1,2,6], [1,3,5], [2,3,4]].

Complexity

• Time: O(C(9, k)) combinations explored — a small constant since digits are capped at 9.
• Space: O(k) recursion depth (plus the output).

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

    private void backtrack(int start, int k, int remaining,
                           List<Integer> path, List<List<Integer>> res) {
        if (k == 0 && remaining == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (k == 0 || remaining <= 0) return;
        for (int d = start; d <= 9; d++) {
            if (d > remaining) break;
            path.add(d);
            backtrack(d + 1, k - 1, remaining - d, path, res);
            path.remove(path.size() - 1);
        }
    }
}