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.