k Distinct Digits That Sum to a Target

medium backtracking

Problem

Return every strictly increasing tuple of k digits drawn from 1..9 whose sum equals n. Backtrack: at each step pick a digit larger than the last; prune when the running sum already exceeds the target or too few digits remain.

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 combos(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 combos(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>> combos(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>> combos(int k, int n) {
    K_ = k; N_ = n;
    res_.clear(); path_.clear();
    dfs(1, n);
    return res_;
}

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