Backtracking Concept and Decision Tree Visualization in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is backtracking in simple terms?

Backtracking is a way to solve problems by trying out choices one by one, and if a choice doesn't work, going back and trying another until the right solution is found.

beginner

How does a decision tree help in backtracking?

A decision tree shows all possible choices and paths you can take. It helps visualize how backtracking tries each path and goes back when a path fails.

intermediate

In backtracking, what does 'pruning' mean?

Pruning means stopping early on a path that won't lead to a solution, so you don't waste time exploring it further.

intermediate

What is the role of recursion in backtracking?

Recursion helps backtracking by calling the same function repeatedly with different choices, making it easy to explore all paths step by step.

beginner

Why is backtracking useful for problems like puzzles and combinations?

Because it tries all possible options in an organized way and finds solutions without missing any, perfect for puzzles and combinations where many choices exist.

What does backtracking do when it hits a dead end?

A Ignores the dead end and continues

B Stops the whole process

C Restarts from the beginning

D Goes back to try a different choice

Backtracking goes back to the previous step to try a different choice when a path fails.

Which data structure best represents all possible choices in backtracking?

A Linked list

B Decision tree

C Stack

D Queue

A decision tree shows all possible choices and paths clearly.

What is pruning in backtracking?

A Adding more choices

B Trying all paths without skipping

C Stopping early on bad paths

D Saving all paths explored

Pruning means stopping early on paths that won't lead to a solution.

How does recursion help in backtracking?

A By repeating the same steps with different choices

B By storing all solutions at once

C By avoiding any repeated work

D By sorting the choices

Recursion calls the same function with different choices to explore all paths.

Which problem type is backtracking NOT typically used for?

A Sorting numbers quickly

B Solving puzzles

C Finding all combinations

D Searching for paths

Backtracking is not used for fast sorting; other algorithms like quicksort are better.

Explain how backtracking uses a decision tree to find solutions.

Think about how each branch represents a choice and how backtracking moves through branches.

Describe the role of recursion and pruning in making backtracking efficient.

Consider how recursion helps explore and pruning helps avoid waste.