Backtracking Concept and Decision Tree Visualization in DSA Typescript - Execution Trace

Concept Flow - Backtracking Concept and Decision Tree Visualization

Start at root decision

↓

Make a choice

↓

Is choice valid?

No→Backtrack to previous choice

|Yes↓

Move to next decision level

↓

All decisions made?

No→Repeat: Make a choice

|Yes↓

Record solution

↓

Backtrack to explore other choices

↓

End

Backtracking tries choices step-by-step, checks if they work, and goes back if stuck, exploring all possibilities like a decision tree.

Execution Sample

DSA Typescript

function backtrack(path: number[], choices: number[]): void {
  if (path.length === 2) {
    console.log(path);
    return;
  }
  for (const choice of choices) {
    path.push(choice);
    backtrack(path, choices);
    path.pop();
  }
}

This code tries all pairs of numbers from choices, printing each pair as a solution.

Execution Table

Step	Operation	Current Path	Action	Decision Tree Visual
1	Start backtrack	[]	Begin with empty path	Root: []
2	Choose 1	[1]	Add 1 to path	Root: [] └─ 1
3	Choose 1 again	[1,1]	Add 1 to path, path length=2, print	Root: [] └─ 1 └─ 1 (Solution)
4	Backtrack	[1]	Remove last choice	Root: [] └─ 1
5	Choose 2	[1,2]	Add 2 to path, path length=2, print	Root: [] └─ 1 └─ 2 (Solution)
6	Backtrack	[1]	Remove last choice	Root: [] └─ 1
7	Backtrack	[]	Remove last choice	Root: []
8	Choose 2	[2]	Add 2 to path	Root: [] └─ 2
9	Choose 1	[2,1]	Add 1 to path, path length=2, print	Root: [] └─ 2 └─ 1 (Solution)
10	Backtrack	[2]	Remove last choice	Root: [] └─ 2
11	Choose 2	[2,2]	Add 2 to path, path length=2, print	Root: [] └─ 2 └─ 2 (Solution)
12	Backtrack	[2]	Remove last choice	Root: [] └─ 2
13	Backtrack	[]	Remove last choice, all choices tried	Root: []
14	End	[]	All paths explored, stop	Root: []

💡 All possible pairs of length 2 from choices [1,2] have been explored and printed.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12	After Step 13	Final
path	[]	[1]	[1,1]	[1]	[1,2]	[1]	[]	[2]	[2,1]	[2]	[2,2]	[2]	[]	[]

Key Moments - 3 Insights

Why do we remove the last choice from path after recursive call?

Because after exploring deeper choices, we must undo the last choice to try other options at the same level, as shown in steps 4, 6, 7, 10, 12, and 13 in the execution_table.

How does backtracking know when to print a solution?

It prints when the path length reaches the target (2 here), as seen in steps 3, 5, 9, and 11 where path length is 2 and the path is printed.

What happens if we don't backtrack properly?

Without removing last choices, the path would keep growing incorrectly and miss exploring all possibilities, breaking the decision tree structure shown in the visual states.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the current path?

A [1,2]

B [1]

C [2]

D [1,1]

💡 Hint

Check the 'Current Path' column at step 5 in the execution_table.

At which step does the algorithm backtrack from path [2,1]?

A Step 9

B Step 10

C Step 11

D Step 12

💡 Hint

Look for the step where path changes from [2,1] to [2] in the variable_tracker and execution_table.

If we change choices to [1,2,3], how many solutions will be printed?

A 6

B 3

C 9

D 12

💡 Hint

Number of pairs of length 2 from 3 choices is 3*3=9, consider all combinations.

Concept Snapshot

Backtracking tries choices step-by-step.
If a choice leads to a dead end, it goes back (backtracks).
It explores all possible paths like a decision tree.
Use recursion with path tracking and undo choices after recursion.
Print or record solutions when a complete valid path is found.

Full Transcript

Backtracking is a method to explore all possible choices step-by-step. We start with an empty path and add choices one by one. If the path reaches the desired length, we record it as a solution. If a choice leads to no solution, we remove it and try another. This process repeats recursively, exploring a decision tree of choices. The code example tries all pairs from choices [1,2]. The execution table shows each step adding or removing choices and printing solutions. Key moments include why we remove choices after recursion and when solutions are printed. The visual quiz tests understanding of path states and backtracking steps. The concept snapshot summarizes backtracking as exploring all paths with recursion and undoing choices to try alternatives.

Practice

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

easy

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

B. Sort data before processing it

C. Use loops to repeat actions without conditions

D. Store data in a fixed-size array

Solution

1. Step 1: Understand backtracking approach

   Backtracking tries all possible choices step-by-step and goes back if a choice fails.

2. Step 2: Compare options with backtracking definition

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

3. Final Answer:

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

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 is just looping
• Believing backtracking stores fixed data only

2. Which of the following is the correct TypeScript function signature for a backtracking function that tries to build a string path?

easy

A. function backtrack(path: number): string

B. function backtrack(path: string): void

C. function backtrack(): number[]

D. function backtrack(path: boolean): boolean

Solution

1. Step 1: Identify expected input and output

   Backtracking often builds a path string and does not return a value, so void return is common.

2. Step 2: Match signature with backtracking pattern

   function backtrack(path: string): void matches a function taking a string path and returning void, which fits backtracking.

3. Final Answer:

   function backtrack(path: string): void -> Option B

4. Quick Check:

   Backtracking function signature = string input, void output [OK]

Hint: Backtracking functions usually return void and take current path [OK]

Common Mistakes:

• Using wrong return types like number or boolean
• Missing input parameter for current path
• Confusing return type with output data

3. Consider this TypeScript backtracking snippet:

function backtrack(path: string, choices: string[]): void {
  if (path.length === 2) {
    console.log(path);
    return;
  }
  for (const choice of choices) {
    backtrack(path + choice, choices);
  }
}
backtrack('', ['A', 'B']);

What will be printed?

medium

A. AA, AB, BA, BB

B. A, B

C. AB, BA

D. AA, BB

Solution

1. Step 1: Understand recursion and stopping condition

   The function prints when path length is 2, building strings by adding 'A' or 'B'.

2. Step 2: Trace all paths of length 2

   Starting empty, choices add 'A' or 'B' twice: 'AA', 'AB', 'BA', 'BB' are printed.

3. Final Answer:

   AA, AB, BA, BB -> Option A

4. Quick Check:

   All 2-length combos of A and B printed [OK]

Hint: Count all 2-letter combos from choices [OK]

Common Mistakes:

• Printing only single letters
• Missing some combinations
• Confusing order of printed strings

4. This backtracking code tries to generate all subsets of [1, 2] but has a bug:

function backtrack(start: number, path: number[], nums: number[]) {
  console.log(path);
  for (let i = start; i < nums.length; i++) {
    path.push(nums[i]);
    backtrack(i, path, nums);
    path.pop();
  }
}
backtrack(0, [], [1, 2]);

What is the bug?

medium

A. start should be initialized to 1

B. path.pop() is missing to undo choice

C. Console.log should be after the loop

D. Recursive call should use i + 1 instead of i to avoid duplicates

Solution

1. Step 1: Analyze recursive call parameter

   The call uses backtrack(i, ...) which reuses the same index, causing repeated subsets.

2. Step 2: Fix recursion to avoid duplicates

   Changing to backtrack(i + 1, ...) moves forward, preventing duplicates and infinite loops.

3. Final Answer:

   Recursive call should use i + 1 instead of i to avoid duplicates -> Option D

4. Quick Check:

   Advance index in recursion = i + 1 [OK]

Hint: Use i + 1 in recursion to move forward [OK]

Common Mistakes:

• Not advancing index causing infinite recursion
• Removing path.pop() causing wrong subsets
• Misplacing console.log outside recursion

5. You want to use backtracking to find all 3-letter strings from letters ['X', 'Y', 'Z'] but without repeating the same letter consecutively. Which change to this code snippet enforces that?

function backtrack(path: string, letters: string[]) {
  if (path.length === 3) {
    console.log(path);
    return;
  }
  for (const letter of letters) {
    // What condition to add here?
    backtrack(path + letter, letters);
  }
}
backtrack('', ['X', 'Y', 'Z']);

hard

A. Add: if (path.length < 3) before recursive call

B. Add: if (letter !== 'X') before recursive call

C. Add: if (path.length === 0 || path[path.length - 1] !== letter) before recursive call

D. Add: if (path.includes(letter)) before recursive call

Solution

1. Step 1: Understand the no consecutive repeat rule

   We must skip adding a letter if it matches the last letter in path.

2. Step 2: Write condition to check last letter

   Condition if path is empty or last letter differs from current letter ensures no repeats.

3. Final Answer:

   Add: if (path.length === 0 || path[path.length - 1] !== letter) before recursive call -> Option C

4. Quick Check:

   Check last letter before adding new letter [OK]

Hint: Check last letter to avoid consecutive repeats [OK]

Common Mistakes:

• Filtering letters incorrectly by fixed letter
• Checking only path length without letter comparison
• Using includes() which disallows all repeats