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.

Practice

1. What does the problem "Generate All Combinations Sum K" ask you to find?

easy

A. The count of numbers equal to K

B. The largest number less than K

C. All unique combinations of numbers that add up to K

D. The smallest number greater than K

Solution

1. Step 1: Understand the problem goal

   The problem asks to find all unique sets of numbers whose sum equals K.

2. Step 2: Clarify uniqueness and sum condition

   Each combination must sum exactly to K without duplicates in the result.

3. Final Answer:

   All unique combinations of numbers that add up to K -> Option C

4. Quick Check:

   Combinations sum to K = All unique combinations of numbers that add up to K [OK]

Hint: Focus on combinations that sum exactly to K [OK]

Common Mistakes:

• Confusing sum with count
• Including duplicate combinations
• Looking for single numbers only

2. Which of the following TypeScript function signatures correctly represents a function to generate all combinations summing to K from an array of numbers?

easy

A. function generateCombinations(nums: number, target: number[]): number[]

B. function generateCombinations(nums: number[], target: number): number[][]

C. function generateCombinations(nums: string[], target: string): string[]

D. function generateCombinations(nums: number[], target: number): number[]

Solution

1. Step 1: Analyze parameter types

   The function should take an array of numbers and a target number.

2. Step 2: Analyze return type

   It should return an array of arrays of numbers representing combinations.

3. Final Answer:

   function generateCombinations(nums: number[], target: number): number[][] -> Option B

4. Quick Check:

   Input array and target number, output array of number arrays [OK]

Hint: Input array and target number, output array of arrays [OK]

Common Mistakes:

• Using wrong parameter types
• Returning flat array instead of array of arrays
• Mixing string and number types

3. What is the output of the following TypeScript code?

function combineSum(nums: number[], target: number): number[][] {
  const result: number[][] = [];
  function backtrack(start: number, path: number[], sum: number) {
    if (sum === target) {
      result.push([...path]);
      return;
    }
    if (sum > target) return;
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path, sum + nums[i]);
      path.pop();
    }
  }
  backtrack(0, [], 0);
  return result;
}

console.log(combineSum([1, 2, 3], 3));

medium

A. [[1, 2], [3]]

B. [[1, 3], [2]]

C. [[3], [2, 1]]

D. [[1, 2, 3]]

Solution

1. Step 1: Trace backtracking calls

   Starting from 0, combinations are built adding numbers without reuse: [1,2] sums to 3, [3] sums to 3.

2. Step 2: Confirm valid combinations

   Other combinations like [2] or [1,3] do not sum to 3 or are invalid due to index increment.

3. Final Answer:

   [[1, 2], [3]] -> Option A

4. Quick Check:

   Combinations summing to 3 = [[1, 2], [3]] [OK]

Hint: Check sums and index increments carefully [OK]

Common Mistakes:

• Including combinations with reused elements
• Ignoring sum > target condition
• Confusing order of elements

4. Identify the bug in this TypeScript function that aims to generate all combinations summing to K:

function findCombos(nums: number[], target: number): number[][] {
  const res: number[][] = [];
  function dfs(i: number, path: number[], total: number) {
    if (total === target) {
      res.push(path);
      return;
    }
    if (total > target || i === nums.length) return;
    dfs(i + 1, path, total);
    path.push(nums[i]);
    dfs(i + 1, path, total + nums[i]);
    path.pop();
  }
  dfs(0, [], 0);
  return res;
}

medium

A. The function does not return any result

B. The base case does not check for total > target

C. The recursion does not increment index i

D. The path array is pushed by reference causing incorrect results

Solution

1. Step 1: Check how path is stored

   The path array is pushed directly without copying, so later changes affect stored results.

2. Step 2: Understand impact on results

   Because path is referenced, all stored combinations end up empty or incorrect after backtracking.

3. Final Answer:

   The path array is pushed by reference causing incorrect results -> Option D

4. Quick Check:

   Push copy of path, not reference [OK]

Hint: Always push a copy of path, not the original [OK]

Common Mistakes:

• Pushing path without copying
• Not handling base cases properly
• Incorrect index increment

5. Given an array with duplicates, how can you modify the combination sum algorithm to generate all unique combinations summing to K without duplicates in the result?

nums = [1, 2, 2, 3], target = 4

hard

A. Sort the array and skip duplicates during recursion

B. Use a Set to store all combinations as strings

C. Allow duplicates and filter results after generation

D. Ignore duplicates and generate all combinations

Solution

1. Step 1: Sort the input array

   Sorting groups duplicates together, making it easier to skip them during recursion.

2. Step 2: Skip duplicates in recursion

   When iterating, skip elements equal to the previous to avoid duplicate combinations.

3. Final Answer:

   Sort the array and skip duplicates during recursion -> Option A

4. Quick Check:

   Sorting + skipping duplicates = unique combinations [OK]

Hint: Sort and skip duplicates while recursing [OK]

Common Mistakes:

• Not sorting before recursion
• Filtering duplicates after generation (inefficient)
• Ignoring duplicates causing repeated results