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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Backtracking Path Generation

What is the output of the following TypeScript code that uses backtracking to generate all subsets of [1, 2]?

DSA Typescript

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

A [[1], [1, 2], [2]]

B [[], [1], [1, 2], [2]]

C [[], [2], [1], [1, 2]]

D [[1, 2], [1], [2], []]

💡 Hint

Think about how the function adds the current path before exploring further.

The function starts with an empty path and adds it to the result. Then it tries adding 1, recurses, then backtracks and tries adding 2. This generates all subsets including the empty set.

🧠 Conceptual

intermediate

Understanding Decision Tree Nodes in Backtracking

In a backtracking decision tree for generating permutations of [1, 2, 3], how many nodes are there in total including the root and all leaves?

A 16

B 15

C 24

D 10

💡 Hint

Count nodes at each level: root, first choice, second choice, and leaves.

For permutations of 3 elements, the tree has 4 levels (including root). Number of nodes = 1 + 3 + 6 + 6 = 16. But the root is counted once, so total nodes are 1 + 3 + 6 + 6 = 16. However, the question includes root and leaves, so 16 is correct.

Rechecking: root (1), level 1 (3), level 2 (6), level 3 (6) total 16 nodes.

🔧 Debug

advanced

Identify the Output of Backtracking with Early Pruning

What is the output of this TypeScript code that generates combinations of [1, 2, 3] of size 2 but prunes paths where sum exceeds 3?

DSA Typescript

function backtrack(start: number, path: number[], result: number[][], sum: number) {
  if (path.length === 2) {
    result.push([...path]);
    return;
  }
  for (let i = start; i < 3; i++) {
    if (sum + i + 1 > 3) continue;
    path.push(i + 1);
    backtrack(i + 1, path, result, sum + i + 1);
    path.pop();
  }
}
const result: number[][] = [];
backtrack(0, [], result, 0);
console.log(result);

A [[1, 2], [1, 3], [2, 3]]

B [[1, 2], [2, 3]]

C [[1, 2]]

D [[1, 2], [1, 3]]

💡 Hint

Check which pairs have sums less than or equal to 3.

The code only adds pairs where the sum is <= 3. The pairs are (1,2)=3, (1,3)=4, (2,3)=5. So only [1, 2] is included.

🚀 Application

advanced

Backtracking to Solve N-Queens: Number of Solutions for N=4

Using backtracking, how many distinct solutions exist for the 4-Queens problem?

A 0

B 4

C 1

D 2

💡 Hint

Try placing queens row by row and count valid configurations.

The 4-Queens problem has exactly 2 distinct solutions where no two queens attack each other.

🧠 Conceptual

expert

Backtracking Decision Tree Depth for Subset Sum Problem

For a set of 5 elements, what is the maximum depth of the backtracking decision tree when solving the subset sum problem?

A 5

B 10

C 6

D 4

💡 Hint

Each element can be either included or excluded, depth corresponds to decisions per element.

The maximum depth equals the number of elements because each element is a decision point: include or exclude.

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