Combination Sum III

medium backtracking

Problem

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. Each number is used at most once. Return a list of all possible valid combinations.

Inputk = 3, n = 9

Output[[1,2,6],[1,3,5],[2,3,4]]

Three tuples of three distinct digits 1–9 summing to 9.

def combination_sum3(k, n):
    res = []
    def dfs(start, path, rem):
        if len(path) == k and rem == 0: res.append(path[:]); return
        if len(path) == k or rem < 0: return
        for d in range(start, 10):
            if d > rem: break
            path.append(d); dfs(d + 1, path, rem - d); path.pop()
    dfs(1, [], n)
    return res

function combinationSum3(k, n) {
  const res = [];
  function dfs(start, path, rem) {
    if (path.length === k && rem === 0) { res.push(path.slice()); return; }
    if (path.length === k || rem < 0) return;
    for (let d = start; d <= 9; d++) {
      if (d > rem) break;
      path.push(d); dfs(d + 1, path, rem - d); path.pop();
    }
  }
  dfs(1, [], n);
  return res;
}

class Solution {
    int K, N;
    List<List<Integer>> res;
    List<Integer> path;
    public List<List<Integer>> combinationSum3(int k, int n) {
        this.K = k; this.N = n;
        res = new ArrayList<>(); path = new ArrayList<>();
        dfs(1, n);
        return res;
    }
    private void dfs(int start, int rem) {
        if (path.size() == K && rem == 0) { res.add(new ArrayList<>(path)); return; }
        if (path.size() == K || rem < 0) return;
        for (int d = start; d <= 9; d++) {
            if (d > rem) break;
            path.add(d); dfs(d + 1, rem - d); path.remove(path.size() - 1);
        }
    }
}

int K_, N_;
vector<vector<int>> res_;
vector<int> path_;
void dfs(int start, int rem) {
    if ((int)path_.size() == K_ && rem == 0) { res_.push_back(path_); return; }
    if ((int)path_.size() == K_ || rem < 0) return;
    for (int d = start; d <= 9; d++) {
        if (d > rem) break;
        path_.push_back(d); dfs(d + 1, rem - d); path_.pop_back();
    }
}
vector<vector<int>> combinationSum3(int k, int n) {
    K_ = k; N_ = n;
    res_.clear(); path_.clear();
    dfs(1, n);
    return res_;
}

Explanation

We need every set of exactly k distinct digits from 1 to 9 that adds up to n. The clean way to enumerate distinct, non-repeating sets is to always pick digits in increasing order.

The function dfs(start, path, rem) builds a combination. start is the smallest digit we are still allowed to use, path is what we have chosen so far, and rem is how much of the target is left. By recursing with d + 1 after choosing d, each digit is used once and the digits stay sorted, so no combination repeats.

Two checks decide when to stop. If len(path) == k and rem == 0 we have a valid answer and record it. If we have already used k digits, or rem has gone negative, this branch can't work so we return. The loop also prunes with if d > rem: break — since digits only grow, once one digit alone exceeds the remainder, the rest are hopeless too.

Example: k = 3, n = 9. Starting from 1 we try 1, 2, 6 (sum 9) → record [1,2,6]. Backtracking gives [1,3,5] and [2,3,4]. Anything starting with a digit too large gets pruned right away.

Because at most a handful of increasing digit choices fit, the search stays small and explores only promising branches.

Time: O(C(9, k)) Space: O(k) recursion