216. Combination Sum 3

Difficulty: MEDIUM

Problem description can be found here.

Approach

Can follow a typical Backtracking problem template.

Solution

function combinationSum3(k: number, n: number): number[][] {
  const result: number[][] = [];

  function backtrack(index: number, path: number[]) {
    const sum = path.reduce((a, b) => a + b, 0);

    if (sum === n && path.length === k) {
      result.push(path.slice());
      return;
    }

    for (let i = index; i < 10; i++) {
      path.push(i);

      if (sum < n && path.length <= k) {
        backtrack(i + 1, path);
      }

      path.pop();
    }
  }

  backtrack(1, []);

  return result;
}

combinationSum3(3, 7);
combinationSum3(3, 9);
combinationSum3(9, 45); // [ [1, 2, 3, 4, 5, 6, 7, 8, 9] ]