Generate All Combinations Sum K in DSA Javascript

Mental Model

Find all groups of numbers from a list that add up exactly to a target number.

Analogy: Imagine you have different coins and want to find all ways to pick some coins so their total value matches a price exactly.

Candidates: [2, 3, 6, 7]
Target: 7

Start with empty combination []
Try adding numbers one by one and check sums:
[]
↓
[2]
↓
[2, 2]
↓
[2, 3]
...
Goal: combinations that sum to 7

Dry Run Walkthrough

Input: candidates: [2, 3, 6, 7], target: 7

Goal: Find all unique combinations of candidates where numbers sum to 7

Step 1: Start with empty combination [] and target 7

[] (target=7)

Why: We begin with no numbers chosen and full target to reach

Step 2: Add 2 to combination: [2], reduce target to 5

[2] (target=5)

Why: Try including 2 and see if we can reach target 7 by adding more

Step 3: Add 2 again: [2, 2], reduce target to 3

[2, 2] (target=3)

Why: We can reuse numbers, so try adding 2 again

Step 4: Add 3: [2, 2, 3], target becomes 0, combination found

[2, 2, 3] (target=0)

Why: Sum matches target, so this combination is valid

Step 5: Backtrack: remove last 3, try next candidate 6 at [2, 2]

[2, 2] (target=3)

Why: Try other numbers after removing last choice

Step 6: 6 is too big for target 3, skip and backtrack to [2]

[2] (target=5)

Why: Cannot add 6 because it exceeds remaining target

Step 7: Add 3 to [2]: [2, 3], target 2

[2, 3] (target=2)

Why: Try adding 3 after 2

Step 8: Add 2 to [2, 3]: [2, 3, 2], target 0, combination found

[2, 3, 2] (target=0)

Why: Sum matches target again, valid combination

Step 9: Backtrack fully and try starting with 3: [3], target 4

[3] (target=4)

Why: Try other starting points

Step 10: Add 3 again: [3, 3], target 1

[3, 3] (target=1)

Why: Try adding 3 multiple times

Step 11: Add 2: [3, 3, 2], target -1 (invalid), backtrack

[3, 3] (target=1)

Why: Sum exceeded target, discard this path

Step 12: Try 6 at [3]: 6 > target 4, skip

[3] (target=4)

Why: Cannot add number larger than remaining target

Step 13: Try 7 at []: [7], target 0, combination found

[7] (target=0)

Why: Single number equals target, valid combination

Result:

[2, 2, 3] -> [7] -> null

Annotated Code

DSA Javascript

class CombinationSum {
  constructor(candidates, target) {
    this.candidates = candidates;
    this.target = target;
    this.result = [];
  }

  backtrack(start, currentCombo, currentSum) {
    if (currentSum === this.target) {
      this.result.push([...currentCombo]); // found valid combo
      return;
    }
    if (currentSum > this.target) {
      return; // sum exceeded target, stop exploring
    }

    for (let i = start; i < this.candidates.length; i++) {
      currentCombo.push(this.candidates[i]); // add candidate
      this.backtrack(i, currentCombo, currentSum + this.candidates[i]); // recurse with updated sum
      currentCombo.pop(); // remove last to backtrack
    }
  }

  findCombinations() {
    this.backtrack(0, [], 0);
    return this.result;
  }
}

// Driver code
const candidates = [2, 3, 6, 7];
const target = 7;
const combSum = new CombinationSum(candidates, target);
const combos = combSum.findCombinations();
for (const combo of combos) {
  console.log(combo.join(' -> ') + ' -> null');
}

if (currentSum === this.target) {

check if current combination sums exactly to target

this.result.push([...currentCombo]);

save a copy of current valid combination

if (currentSum > this.target) {

stop exploring if sum exceeds target

for (let i = start; i < this.candidates.length; i++) {

try candidates from current start index to avoid duplicates

currentCombo.push(this.candidates[i]);

add candidate to current combination

this.backtrack(i, currentCombo, currentSum + this.candidates[i]);

recurse allowing reuse of same candidate

currentCombo.pop();

remove last candidate to backtrack and try next

Output

2 -> 2 -> 3 -> null

7 -> null

Complexity Analysis

Time: O(2^n) because each candidate can be chosen or not, leading to exponential combinations

Space: O(k) where k is the depth of recursion equal to max combination length

vs Alternative: Compared to brute force checking all subsets, backtracking prunes paths early when sum exceeds target, saving time

Edge Cases

empty candidates array

returns empty list since no combinations possible

DSA Javascript

for (let i = start; i < this.candidates.length; i++) {

target is zero

returns list with empty combination as valid

DSA Javascript

if (currentSum === this.target) {

candidates contain duplicates

algorithm still works but may produce duplicate combinations if input not unique

DSA Javascript

for (let i = start; i < this.candidates.length; i++) {

When to Use This Pattern

When asked to find all combinations of numbers that sum to a target, use backtracking to explore choices and prune invalid paths.

Common Mistakes

Mistake: Not allowing reuse of the same candidate leads to missing valid combinations
Fix: In recursive call, pass current index 'i' instead of 'i+1' to allow reuse

Mistake: Not backtracking (removing last element) after recursion causes incorrect combinations
Fix: Always pop last element after recursive call to restore state

Summary

Finds all unique combinations of numbers that add up to a target sum.

Use when you need every possible group of numbers summing to a specific value.

The key is to try adding each number, recurse, and backtrack when sum is too big or combination is complete.

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