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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of combinations summing to 4 from [1,2,3]

What is the output of the following code that generates all combinations of numbers from [1,2,3] that sum to 4? The output is an array of arrays, each inner array is one combination.

DSA Javascript

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

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

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

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

C [[1,3]]

D [[1,2,3]]

💡 Hint

Think about combinations where numbers add exactly to 4 without repetition.

The function finds combinations of unique numbers from the array that sum to 4. Only [1,3] sums to 4. [2,2] is invalid because 2 appears only once in the input. [4] is not in the input. [1,2,3] sums to 6, not 4.

🧠 Conceptual

intermediate

Number of combinations summing to 5 from [1,2,3,4]

How many unique combinations of numbers from [1,2,3,4] sum exactly to 5? Each number can be used only once per combination.

A 3

B 2

C 5

D 6

💡 Hint

Try to list all combinations manually.

The valid combinations are [1,4] and [2,3]. [1,2,2] is invalid due to repetition. [1,2,3] sums to 6. [5] is not in the array. Thus, there are 2 combinations.

❓ Predict Output

advanced

Output of combinations summing to 7 with duplicates allowed

What is the output of this code that generates all combinations of numbers from [2,3,6,7] that sum to 7? Numbers can be used multiple times.

DSA Javascript

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

console.log(combinationSum([2,3,6,7], 7));

A [[2,2,3],[7]]

B [[7]]

C [[2,2,3],[3,3,3],[7]]

D [[2,3,6],[7]]

💡 Hint

Numbers can repeat, but combinations must sum exactly to 7.

The combinations are [2,2,3] and [7]. [3,3,3] sums to 9, too big. [2,3,6] sums to 11, too big.

🔧 Debug

advanced

Identify the error in combination sum code

What error does this code produce when trying to generate combinations summing to 5 from [1,2,3]?

DSA Javascript

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

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

A The output contains duplicate references to the same path array

B SyntaxError due to missing colon

C TypeError because path is undefined

D No output because infinite recursion

💡 Hint

Look at how the path array is added to the result.

The code pushes the path array directly without copying it. Since path is mutated later, all entries in result point to the same array, causing duplicates.

🧠 Conceptual

expert

Minimum number of elements in combinations summing to 8 from [1,3,5]

What is the minimum number of elements in any combination of numbers from [1,3,5] that sum exactly to 8? Numbers can be used multiple times.

A 5

B 3

C 4

D 2

💡 Hint

Try to find combinations with fewest numbers summing to 8.

[3,5] sums to 8 with 2 elements. No single element reaches 8 (max 5). Thus, the minimum is 2.

Practice

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

easy

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

B. The largest number less than K

C. The count of numbers greater than K

D. The product of all numbers up to K

Solution

1. Step 1: Understand the problem goal

   The problem asks to find all unique sets of numbers that sum exactly to K.

2. Step 2: Clarify what combinations mean

   Combinations mean groups of numbers without regard to order, all adding to K.

3. Final Answer:

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

4. Quick Check:

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

Hint: Focus on sums equal to K, not counts or products [OK]

Common Mistakes:

• Confusing combinations with permutations
• Looking for counts instead of actual combinations
• Trying to find products instead of sums

2. Which of the following is the correct way to start a recursive function in JavaScript to generate combinations summing to K?

easy

A. function findCombos() { return; }

B. function findCombos(nums, target) { return nums + target; }

C. function findCombos(nums, target, start, path, result) { ... }

D. function findCombos(nums) { console.log(target); }

Solution

1. Step 1: Identify correct recursive function signature

   The function needs parameters for numbers, target sum, start index, current path, and result storage.

2. Step 2: Check options for these parameters

   Only function findCombos(nums, target, start, path, result) { ... } includes all necessary parameters for recursion and backtracking.

3. Final Answer:

   function findCombos(nums, target, start, path, result) { ... } -> Option C

4. Quick Check:

   Recursive function with all params = function findCombos(nums, target, start, path, result) { ... } [OK]

Hint: Include start index and path for backtracking recursion [OK]

Common Mistakes:

• Missing parameters needed for recursion
• Returning wrong values instead of building combinations
• Not including start index to avoid duplicates

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

function combinationSum(nums, target) {
  const result = [];
  function backtrack(start, path, sum) {
    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(combinationSum([2,3,6,7], 7));

medium

A. [[7]]

B. [[2,3,6,7]]

C. [[2,3,7]]

D. [[2,2,3]]

Solution

1. Step 1: Understand the code logic

   The function finds combinations of numbers from the array that sum to 7 without reuse (i + 1).

2. Step 2: Trace the combinations

   Only 7 alone sums to 7; others like 2+3=5, 2+3+6=11 exceed or don't match target.

3. Final Answer:

   [[7]] -> Option A

4. Quick Check:

   Only [7] sums to 7 without repeats = [[7]] [OK]

Hint: Check sum and index increment to avoid reuse [OK]

Common Mistakes:

• Assuming numbers can be reused multiple times
• Including combinations that exceed target
• Not copying path array before pushing

4. Identify the bug in this code snippet for generating combinations summing to K:

function findCombos(nums, target) {
  const result = [];
  function backtrack(start, path, sum) {
    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;
}

medium

A. The base case sum === target is missing

B. The path array is pushed directly without copying, causing reference issues

C. The loop should start from 0 instead of start

D. The function does not return any result

Solution

1. Step 1: Check how results are stored

   The code pushes 'path' directly, which is a reference and will change later.

2. Step 2: Identify correct way to store combinations

   Must push a copy of path (e.g., [...path]) to save current state.

3. Final Answer:

   The path array is pushed directly without copying, causing reference issues -> Option B

4. Quick Check:

   Push copy of path, not reference = The path array is pushed directly without copying, causing reference issues [OK]

Hint: Always push a copy of path array to result [OK]

Common Mistakes:

• Pushing path reference instead of copy
• Incorrect loop start index causing duplicates
• Missing base case for sum equal to target

5. Given the array [1, 2, 3, 4] and target sum 5, which of the following is the correct set of all unique combinations that sum to 5, assuming numbers can be used only once?

hard

A. [[1,2,2]]

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

C. [[5]]

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

Solution

1. Step 1: List all combinations without reuse that sum to 5

   Possible pairs: 1+4=5, 2+3=5; triples or singles don't sum to 5 without reuse.

2. Step 2: Verify options against these combinations

   [[1,4],[2,3]] matches these pairs exactly; others include duplicates or invalid sums.

3. Final Answer:

   [[1,4],[2,3]] -> Option D

4. Quick Check:

   Unique pairs summing to 5 = [[1,4],[2,3]] [OK]

Hint: Sum pairs without reuse to find valid combos [OK]

Common Mistakes:

• Including repeated numbers when only single use allowed
• Assuming single number 5 exists in array
• Counting invalid sums or duplicates