Backtracking Concept and Decision Tree Visualization in DSA Javascript - Time & Space Complexity

Time Complexity: Backtracking Concept and Decision Tree Visualization

O(n!)

Understanding Time Complexity

Backtracking explores many possible choices step-by-step to find solutions.

We want to know how the time needed grows as the number of choices and steps increase.

Scenario Under Consideration

Analyze the time complexity of the following backtracking code snippet.

function backtrack(choices, path) {
  if (path.length === choices.length) {
    console.log(path.join(''));
    return;
  }
  for (let i = 0; i < choices.length; i++) {
    if (!path.includes(choices[i])) {
      path.push(choices[i]);
      backtrack(choices, path);
      path.pop();
    }
  }
}
backtrack(['A', 'B', 'C'], []);
    

This code tries all possible orderings of the choices without repeats, printing each complete path.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop tries each unused choice at every step.
• How many times: It repeats recursively for each position, exploring all permutations.

How Execution Grows With Input

Each step tries all remaining choices, so the total tries multiply quickly.

Input Size (n)	Approx. Operations
3	6 (3 x 2 x 1)
4	24 (4 x 3 x 2 x 1)
5	120 (5 x 4 x 3 x 2 x 1)

Pattern observation: The operations grow very fast, multiplying by one less choice each step.

Final Time Complexity

Time Complexity: O(n!)

This means the time grows very fast as the number of choices increases, because it tries every possible order.

Common Mistake

[X] Wrong: "Backtracking only takes linear time because it uses loops and recursion."

[OK] Correct: Backtracking explores many combinations, so the total tries multiply, not just add up.

Interview Connect

Understanding backtracking time helps you explain how algorithms explore choices and why some problems take longer.

Self-Check

"What if we added pruning to stop early when a path is invalid? How would the time complexity change?"

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