Backtracking Concept and Decision Tree Visualization in DSA Javascript

Mental Model

Backtracking tries choices one by one and goes back if a choice leads to a dead end.

Analogy: Imagine walking through a maze and marking your path. If you hit a wall, you return to the last fork and try a different path.

Start
  ↓
Choice 1 -> Dead end
  ↓
Backtrack ← Choice 2 -> Continue
  ↓
Goal

Dry Run Walkthrough

Input: Find all subsets of [1, 2] using backtracking

Goal: List all possible subsets by choosing or skipping each element

Step 1: Start with empty subset []

[] ↑ (current subset)

Why: We begin with no elements chosen

Step 2: Choose 1, subset becomes [1]

[1] ↑

Why: Try including first element

Step 3: Choose 2, subset becomes [1, 2]

[1, 2] ↑

Why: Try including second element after first

Step 4: Backtrack: remove 2, subset back to [1]

[1] ↑

Why: Try skipping second element after first

Step 5: Backtrack: remove 1, subset back to []

[] ↑

Why: Try skipping first element

Step 6: Choose 2, subset becomes [2]

[2] ↑

Why: Try including second element without first

Step 7: Backtrack: remove 2, subset back to []

[] ↑

Why: Try skipping second element as well

Result:

[] -> [1] -> [1, 2] -> [1] -> [] -> [2] -> []
All subsets found

Annotated Code

DSA Javascript

class Backtracking {
  constructor() {
    this.result = [];
  }

  findSubsets(nums) {
    this.result = [];
    this.backtrack(nums, 0, []);
    return this.result;
  }

  backtrack(nums, index, current) {
    this.result.push([...current]); // save current subset

    for (let i = index; i < nums.length; i++) {
      current.push(nums[i]); // choose element
      this.backtrack(nums, i + 1, current); // explore further
      current.pop(); // backtrack: remove last chosen
    }
  }
}

const bt = new Backtracking();
const subsets = bt.findSubsets([1, 2]);
for (const subset of subsets) {
  console.log(subset.length === 0 ? '[]' : '[' + subset.join(', ') + ']');
}

this.result.push([...current]); // save current subset

Record the current choice path as a valid subset

current.push(nums[i]); // choose element

Add next element to current subset to explore deeper

this.backtrack(nums, i + 1, current); // explore further

Move forward to next index to continue building subset

current.pop(); // backtrack: remove last chosen

Undo last choice to try alternative paths

Output

[]

[1]

[1, 2]

[2]

Complexity Analysis

Time: O(2^n) because each element can be either included or excluded, doubling the number of subsets

Space: O(n) for the recursion stack and current subset storage

vs Alternative: Compared to iterative methods, backtracking cleanly explores all combinations without extra bookkeeping

Edge Cases

Empty input array

Returns one subset: the empty subset []

DSA Javascript

this.result.push([...current]); // save current subset

Single element array

Returns two subsets: [] and [element]

DSA Javascript

for (let i = index; i < nums.length; i++) {

When to Use This Pattern

When you need to explore all possible choices and undo decisions to try alternatives, backtracking is the pattern to use.

Common Mistakes

Mistake: Not removing the last chosen element after recursive call (missing backtrack step)
Fix: Add current.pop() after recursive call to undo the choice

Mistake: Modifying the current subset without copying when saving results
Fix: Save a copy of current subset using [...current] to avoid mutation issues

Summary

Backtracking tries all choices by exploring and undoing decisions to find all solutions.

Use it when you need to explore all combinations, permutations, or subsets.

The key is to choose, explore deeper, then undo the choice to try other options.

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