Generate All Combinations Sum K in DSA Javascript - Execution Trace

Concept Flow - Generate All Combinations Sum K

Start with empty combination

↓

Choose next number from candidates

↓

Add number to current combination

↓

Check sum of combination

↓

Continue

↓

Backtrack: Remove last number

↩Back to Choose next number

We build combinations by adding numbers step-by-step, checking sums, saving when sum equals K, and backtracking to explore all options.

Execution Sample

DSA Javascript

function combSumK(candidates, k) {
  const result = [];
  function backtrack(start, combo, sum) {
    if (sum === k) result.push([...combo]);
    if (sum >= k) return;
    for (let i = start; i < candidates.length; i++) {
      combo.push(candidates[i]);
      backtrack(i + 1, combo, sum + candidates[i]);
      combo.pop();
    }
  }
  backtrack(0, [], 0);
  return result;
}

This code finds all unique combinations of numbers from candidates that sum to k, using backtracking.

Execution Table

Step	Operation	Current Combination	Sum	Action	Visual State
1	Start backtrack(0, [], 0)	[]	0	Begin with empty combo	[]
2	Add 2	[2]	2	Sum < 7, continue	[2]
3	Add 3	[2,3]	5	Sum < 7, continue	[2 -> 3]
4	Add 6	[2,3,6]	11	Sum > 7, backtrack	[2 -> 3 -> 6]
5	Remove 6	[2,3]	5	Backtrack	[2 -> 3]
6	Add 7	[2,3,7]	12	Sum > 7, backtrack	[2 -> 3 -> 7]
7	Remove 7	[2,3]	5	Backtrack	[2 -> 3]
8	Remove 3	[2]	2	Backtrack	[2]
9	Add 6	[2,6]	8	Sum > 7, backtrack	[2 -> 6]
10	Remove 6	[2]	2	Backtrack	[2]
11	Add 7	[2,7]	9	Sum > 7, backtrack	[2 -> 7]
12	Remove 7	[2]	2	Backtrack	[2]
13	Remove 2	[]	0	Backtrack	[]
14	Add 3	[3]	3	Sum < 7, continue	[3]
15	Add 6	[3,6]	9	Sum > 7, backtrack	[3 -> 6]
16	Remove 6	[3]	3	Backtrack	[3]
17	Add 7	[3,7]	10	Sum > 7, backtrack	[3 -> 7]
18	Remove 7	[3]	3	Backtrack	[3]
19	Remove 3	[]	0	Backtrack	[]
20	Add 6	[6]	6	Sum < 7, continue	[6]
21	Add 7	[6,7]	13	Sum > 7, backtrack	[6 -> 7]
22	Remove 7	[6]	6	Backtrack	[6]
23	Remove 6	[]	0	Backtrack	[]
24	Add 7	[7]	7	Sum == 7, save combo	[7]
25	Remove 7	[]	0	Backtrack	[]
26	End	[]	0	All combinations checked	[]

💡 All candidates explored, backtracked fully, and all combos summing to 7 found.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 8	After Step 14	After Step 20	After Step 24	Final
combo	[]	[2]	[2,3,6]	[2]	[3]	[6]	[7]	[]
sum	0	2	11	2	3	6	7	0
result	[]	[]	[]	[]	[]	[]	[[7]]	[[7]]
start	0	0	2	2	3	6	7	0

Key Moments - 3 Insights

Why do we backtrack (remove last number) after each recursive call?

Because after exploring combinations with a number added, we remove it to try other numbers. See steps 4 to 5 and 24 to 25 in execution_table where combo changes back.

Why do we stop exploring when sum >= k?

Because adding more numbers will only increase sum, so no need to continue. See steps 4 and 6 where sum > 7 causes backtrack.

How do we ensure combinations are unique and no duplicates appear?

By starting next recursion from i+1 index, we avoid reusing previous numbers. This is shown in the code and reflected in execution_table where start index increases.

Visual Quiz - 3 Questions

Look at the execution_table at step 24, what is the current combination?

A [6,7]

B [7]

C [2,3]

D []

💡 Hint

Check the 'Current Combination' column at step 24 in execution_table.

At which step does the sum first exceed the target k=7?

A Step 3

B Step 6

C Step 4

D Step 10

💡 Hint

Look for the first step where 'Sum' column is greater than 7 in execution_table.

If we remove the line 'combo.pop()', how would the 'combo' variable change after step 5?

A It would remain [2,3,6]

B It would be []

C It would be [2]

D It would be [3,6]

💡 Hint

Refer to variable_tracker and execution_table steps 4 and 5 showing combo before and after pop.

Concept Snapshot

Generate All Combinations Sum K:
- Use backtracking to build combos
- Add numbers, track sum
- If sum == K, save combo
- If sum > K, backtrack
- Remove last number to try others
- Start next recursion from next index to avoid duplicates

Full Transcript

This visualization shows how to generate all combinations of numbers from a list that sum to a target K. We start with an empty combination and add numbers one by one. After each addition, we check the sum. If the sum equals K, we save the combination. If the sum exceeds K, we stop exploring that path and backtrack by removing the last number added. We then try other numbers by moving forward in the list. This process continues until all combinations are explored. The execution table tracks each step, showing the current combination, sum, and actions taken. The variable tracker shows how the combination and sum change over time. Key moments clarify why backtracking is needed, why we stop when sum exceeds K, and how duplicates are avoided. The quiz tests understanding of these steps. This method ensures all unique combinations summing to K are found efficiently.

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