Backtracking Concept and Decision Tree Visualization in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is backtracking in simple terms?

Backtracking is a way to solve problems by trying out choices one by one and going back if a choice does not work, like exploring paths in a maze and returning when hitting a dead end.

beginner

What does a decision tree represent in backtracking?

A decision tree shows all possible choices at each step and the paths taken, helping visualize how backtracking explores different options to find solutions.

intermediate

How does backtracking decide when to go back or continue?

Backtracking continues forward when choices are valid and goes back (undoes the last choice) when it reaches a dead end or invalid state.

intermediate

In backtracking, what is the role of recursion?

Recursion helps backtracking by calling the same function repeatedly with different choices, making it easy to explore all paths and backtrack when needed.

beginner

Why is backtracking useful for problems like puzzles and combinations?

Because it tries all possible options in an organized way and stops exploring paths that won't lead to a solution, saving time and effort.

What does backtracking do when it hits a dead end?

A It continues forward anyway

B It stops and returns no solution

C It goes back to try a different choice

D It restarts from the beginning

Backtracking goes back to the previous step to try a different choice when it hits a dead end.

What structure helps visualize all choices in backtracking?

A Queue

B Linked list

C Stack

D Decision tree

A decision tree shows all possible choices and paths in backtracking.

Which programming technique is commonly used to implement backtracking?

A Iteration only

B Recursion

C Sorting

D Hashing

Recursion allows backtracking to explore choices and return when needed.

Backtracking is especially useful for which type of problems?

A Puzzles and combinations

B Simple arithmetic

C Sorting numbers

D Searching in arrays

Backtracking helps solve puzzles and combinations by exploring all options.

What happens if a choice in backtracking is valid?

A Backtracking continues forward

B Backtracking goes back immediately

C Backtracking stops

D Backtracking ignores it

If a choice is valid, backtracking moves forward to explore further choices.

Explain how backtracking uses a decision tree to find solutions.

Think about how you explore paths in a maze.

Describe the role of recursion in backtracking algorithms.

Recursion helps repeat the same process with new choices.

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