#216 - Combination Sum III

MediumBacktracking

Find all valid combinations of k numbers that sum up to n, where only digits 1 through 9 are used and each digit is used at most once. Return the list of all valid combinations.

Input	Output
k = 3, n = 7	[[1,2,4]]
k = 3, n = 9	[[1,2,6],[1,3,5],[2,3,4]]
k = 4, n = 1	[]

Solution Space

Try it

/**
 * Finds all combinations of k digits (1-9) that sum to n.
 *
 * @param k Number of digits to pick
 * @param n Target sum
 * @returns All valid combinations
 */
export function combinationSum3(k: number, n: number): number[][] {
  const result: number[][] = [];

  function backtrack(start: number, remaining: number, path: number[]): void {
    if (path.length === k) {
      if (remaining === 0) result.push([...path]);
      return;
    }

    for (let i = start; i <= 9; i++) {
      if (i > remaining) break; // pruning
      path.push(i);
      backtrack(i + 1, remaining - i, path);
      path.pop();
    }
  }

  backtrack(1, n, []);
  return result;
}

Approach: backtracking over digits 1-9 – pick each digit at most once (advance `start`), prune when the current digit exceeds the remaining sum or the path already has `k` elements.

Time: O(C(9, k)) – bounded by the number of k-element subsets of {1…9}.

Space: O(k) – recursion depth and path length.

#39 Combination Sum

#139 Word Break