Backtracking Concept and Decision Tree Visualization in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Backtracking Path Exploration

What is the output of the following JavaScript backtracking code that explores all subsets of [1, 2]?

DSA Javascript

function backtrack(start, path) {
  if (start === 2) {
    console.log(path.join('->') || 'empty');
    return;
  }
  backtrack(start + 1, path);
  backtrack(start + 1, [...path, start + 1]);
}
backtrack(0, []);

A

empty
1->2
1
2

B

empty
2
1
1->2

C

empty
1
2
1->2

D

1
2
empty
1->2

💡 Hint

Trace the recursive calls and note when the base case prints the path.

The function explores subsets by either skipping or including the next number. The base case prints the current path or 'empty' if none.

Order of prints is: empty (no elements), then subset with 2, then subset with 1, then subset with 1 and 2.

🧠 Conceptual

intermediate

Number of Nodes in Backtracking Decision Tree

For a backtracking algorithm that makes two choices at each step for n steps, how many total nodes are in the decision tree?

A n^2

B 2^n

C 2^n - 1

D n!

💡 Hint

Each step doubles the number of nodes except the root.

At each step, the tree branches into 2 choices, so total nodes are sum of 2^0 + 2^1 + ... + 2^(n-1) = 2^n - 1.

🔧 Debug

advanced

Identify the Output of Backtracking with Pruning

What is the output of this JavaScript code that backtracks with pruning to find subsets summing to 3 from [1,2,3]?

DSA Javascript

function backtrack(start, path, sum) {
  if (sum > 3) return;
  if (sum === 3) {
    console.log(path.join('->'));
    return;
  }
  for (let i = start; i < 3; i++) {
    backtrack(i + 1, [...path, i + 1], sum + i + 1);
  }
}
backtrack(0, [], 0);

A

1->2
3

B

3
2->1

C

1->3
2->3

D 1->2->3

💡 Hint

Check which subsets sum exactly to 3 and are printed.

The code prints subsets whose sum is exactly 3. The subsets are [1,2] and [3].

📝 Syntax

advanced

Output of Backtracking with Early Return

What is the output of this JavaScript backtracking code that stops after finding the first subset summing to 3 from [1,2,3]?

DSA Javascript

function backtrack(start, path, sum) {
  if (sum === 3) {
    console.log(path.join('->'));
    return true;
  }
  if (sum > 3) return false;
  for (let i = start; i < 3; i++) {
    if (backtrack(i + 1, [...path, i + 1], sum + i + 1)) return true;
  }
  return false;
}
backtrack(0, [], 0);

A 1->2

B 3

C 1->3

D 2->3

💡 Hint

The code stops at the first subset summing to 3 found in order.

The first subset found with sum 3 is [1,2], so it prints '1->2' and stops.

🚀 Application

expert

Number of Valid Paths in a Backtracking Maze

Consider a 2x2 grid maze where you can move only right or down from the top-left corner to the bottom-right corner. Using backtracking, how many unique paths exist?

A 2

B 4

C 3

D 6

💡 Hint

Count all sequences of moves right (R) and down (D) to reach bottom-right.

From top-left to bottom-right in a 2x2 grid, you must move 2 rights and 2 downs in any order. Number of unique paths is combinations of 4 moves taken 2 at a time: C(4,2) = 6.

But since grid is 2x2 (3 rows and 3 columns points), actually moves needed are 2 rights and 2 downs, so total paths = 6.

Practice

1. What is the main idea behind backtracking in algorithms?

easy

A. Store data in a fixed-size array

B. Sort data before processing it

C. Use loops to repeat actions without stopping

D. Try all possible options and undo choices when they lead to dead ends

Solution

1. Step 1: Understand backtracking process

   Backtracking tries options one by one and goes back if a choice fails.

2. Step 2: Compare options with backtracking idea

   Only Try all possible options and undo choices when they lead to dead ends describes trying and undoing choices, which matches backtracking.

3. Final Answer:

   Try all possible options and undo choices when they lead to dead ends -> Option D

4. Quick Check:

   Backtracking = Try and undo choices [OK]

Hint: Backtracking means try, fail, undo, and try again [OK]

Common Mistakes:

• Confusing backtracking with sorting
• Thinking backtracking only uses loops
• Assuming backtracking stores fixed data

2. Which of the following is the correct syntax to start a backtracking function in JavaScript?

easy

A. backtrack function(options) { }

B. function backtrack(options) { }

C. function: backtrack(options) { }

D. def backtrack(options):

Solution

1. Step 1: Identify JavaScript function syntax

   JavaScript functions start with the keyword function followed by name and parameters.

2. Step 2: Check each option

   function backtrack(options) { } matches correct JavaScript syntax. Options B and C are invalid syntax. def backtrack(options): is Python syntax.

3. Final Answer:

   function backtrack(options) { } -> Option B

4. Quick Check:

   JS function syntax = function name(params) [OK]

Hint: JS functions start with 'function' keyword [OK]

Common Mistakes:

• Using Python syntax in JavaScript
• Misplacing the function keyword
• Using colons instead of braces

3. What will be the output of the following code snippet?

function backtrack(path, options) {
  if (path.length === 2) {
    console.log(path);
    return;
  }
  for (let i = 0; i < options.length; i++) {
    backtrack(path + options[i], options);
  }
}
backtrack('', ['a', 'b']);

medium

A. ['aa', 'ab', 'ba', 'bb']

B. ['a', 'b']

C. ['ab', 'ba']

D. ['a', 'aa', 'ab', 'b', 'ba', 'bb']

Solution

1. Step 1: Understand recursion and path building

   The function adds one character from options each call until path length is 2, then prints path.

2. Step 2: Trace calls and outputs

   Paths generated: 'aa', 'ab', 'ba', 'bb' as it tries both 'a' and 'b' at each step.

3. Final Answer:

   ['aa', 'ab', 'ba', 'bb'] -> Option A

4. Quick Check:

   All 2-letter combos from 'a' and 'b' = ['aa','ab','ba','bb'] [OK]

Hint: Backtracking tries all combos of length 2 here [OK]

Common Mistakes:

• Thinking only unique letters appear
• Confusing path length with options length
• Missing repeated letters in output

4. Find the error in this backtracking code that tries to generate subsets:

function subsets(nums, path = []) {
  if (nums.length === 0) {
    console.log(path);
    return;
  }
  subsets(nums.slice(1), path);
  subsets(nums.slice(1), path.push(nums[0]));
}
subsets([1, 2]);

medium

A. Console.log should be outside the function

B. Missing base case for empty path

C. Using path.push(nums[0]) modifies path and returns length, not array

D. Should use nums.pop() instead of nums.slice(1)

Solution

1. Step 1: Understand path.push behavior

   path.push(nums[0]) changes path array but returns new length, not updated array.

2. Step 2: Identify correct recursive call

   Passing path.push(nums[0]) as argument passes a number, causing wrong recursion.

3. Final Answer:

   Using path.push(nums[0]) modifies path and returns length, not array -> Option C

4. Quick Check:

   push() returns length, not array [OK]

Hint: push() returns length, not updated array [OK]

Common Mistakes:

• Assuming push returns the array
• Ignoring side effects on path array
• Confusing slice and pop usage

5. Given a decision tree for solving a maze using backtracking, which strategy helps avoid revisiting the same cell and infinite loops?

hard

A. Mark visited cells and skip them in future steps

B. Always move right before other directions

C. Use a queue instead of recursion

D. Restart the maze from the beginning after each dead end

Solution

1. Step 1: Understand infinite loops in maze backtracking

   Revisiting same cells causes loops; marking visited cells prevents this.

2. Step 2: Evaluate options for avoiding revisits

   Mark visited cells and skip them in future steps marks visited cells to skip them, stopping loops. Others do not prevent revisits effectively.

3. Final Answer:

   Mark visited cells and skip them in future steps -> Option A

4. Quick Check:

   Visited marking prevents infinite loops [OK]

Hint: Mark visited spots to avoid loops [OK]

Common Mistakes:

• Thinking direction order avoids loops
• Confusing recursion with queue usage
• Restarting maze wastes time, doesn't prevent loops