Generate All Combinations Sum K in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of combinations summing to K

What is the output of the following TypeScript code that generates all combinations of numbers from 1 to 9 that sum to 5?

DSA Typescript

function combinationSumK(k: number, n: number): number[][] {
  const result: number[][] = [];
  function backtrack(start: number, target: number, path: number[]) {
    if (target === 0 && path.length === k) {
      result.push([...path]);
      return;
    }
    if (target < 0 || path.length > k) {
      return;
    }
    for (let i = start; i <= 9; i++) {
      path.push(i);
      backtrack(i + 1, target - i, path);
      path.pop();
    }
  }
  backtrack(1, n, []);
  return result;
}

console.log(combinationSumK(2, 5));

A [[1,4],[2,3],[1,2,2]]

B [[1,4],[2,3],[5]]

C [[1,4],[3,2]]

D [[1,4],[2,3]]

💡 Hint

Focus on combinations of exactly 2 numbers that add up to 5.

The function finds all unique combinations of 2 numbers from 1 to 9 that sum to 5. The valid pairs are [1,4] and [2,3]. The function does not include single numbers or repeated numbers.

❓ Predict Output

intermediate

Number of combinations for sum and length

How many combinations of 3 numbers from 1 to 9 sum to 9 using the given function?

DSA Typescript

function combinationSumK(k: number, n: number): number[][] {
  const result: number[][] = [];
  function backtrack(start: number, target: number, path: number[]) {
    if (target === 0 && path.length === k) {
      result.push([...path]);
      return;
    }
    if (target < 0 || path.length > k) {
      return;
    }
    for (let i = start; i <= 9; i++) {
      path.push(i);
      backtrack(i + 1, target - i, path);
      path.pop();
    }
  }
  backtrack(1, n, []);
  return result;
}

const combos = combinationSumK(3, 9);
console.log(combos.length);

A 2

B 4

C 3

D 5

💡 Hint

List all 3-number combinations from 1 to 9 that sum to 9.

The valid combinations are [1,2,6], [1,3,5], [2,3,4]. These are the only strictly increasing combinations of 3 distinct numbers from 1 to 9 that sum to 9. Hence, there are 3 combinations.

🔧 Debug

advanced

Identify the error in combination sum code

What error will this TypeScript code produce when run?

DSA Typescript

function combinationSumK(k: number, n: number): number[][] {
  const result: number[][] = [];
  function backtrack(start: number, target: number, path: number[]) {
    if (target === 0 && path.length === k) {
      result.push(path);
      return;
    }
    if (target < 0 || path.length > k) {
      return;
    }
    for (let i = start; i <= 9; i++) {
      path.push(i);
      backtrack(i + 1, target - i, path);
      path.pop();
    }
  }
  backtrack(1, n, []);
  return result;
}

console.log(combinationSumK(3, 7));

A No error, outputs correct combinations

B Output contains references to the same array multiple times

C TypeError: path.push is not a function

D SyntaxError: Unexpected token

💡 Hint

Check how arrays are added to the result.

The code pushes the same 'path' array reference to the result multiple times without copying it. Later modifications to 'path' affect all stored references, causing incorrect results.

❓ Predict Output

advanced

Output of combinationSumK with no valid combinations

What is the output of the following code when no combinations of length 4 sum to 3?

DSA Typescript

function combinationSumK(k: number, n: number): number[][] {
  const result: number[][] = [];
  function backtrack(start: number, target: number, path: number[]) {
    if (target === 0 && path.length === k) {
      result.push([...path]);
      return;
    }
    if (target < 0 || path.length > k) {
      return;
    }
    for (let i = start; i <= 9; i++) {
      path.push(i);
      backtrack(i + 1, target - i, path);
      path.pop();
    }
  }
  backtrack(1, n, []);
  return result;
}

console.log(combinationSumK(4, 3));

A []

B [[]]

C [[1,1,1,0]]

D null

💡 Hint

Can 4 positive distinct numbers sum to 3?

No 4 distinct positive numbers can sum to 3, so the result array remains empty.

🚀 Application

expert

Find all combinations of length 3 summing to 9

Using the combinationSumK function, which of the following is the complete set of combinations of length 3 that sum to 9?

DSA Typescript

function combinationSumK(k: number, n: number): number[][] {
  const result: number[][] = [];
  function backtrack(start: number, target: number, path: number[]) {
    if (target === 0 && path.length === k) {
      result.push([...path]);
      return;
    }
    if (target < 0 || path.length > k) {
      return;
    }
    for (let i = start; i <= 9; i++) {
      path.push(i);
      backtrack(i + 1, target - i, path);
      path.pop();
    }
  }
  backtrack(1, n, []);
  return result;
}

console.log(combinationSumK(3, 9));

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

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

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

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

💡 Hint

Check that numbers are distinct and combinations are sorted ascending.

The function generates combinations of distinct numbers in ascending order. The valid combinations of length 3 summing to 9 are [1,2,6], [1,3,5], and [2,3,4]. Options with repeated numbers or incorrect sums are invalid.