Why Backtracking and What Greedy Cannot Solve in DSA Typescript - Quick Recap

Recall & Review

beginner

What is the main idea behind backtracking?

Backtracking tries all possible options step-by-step and goes back (undoes) when a choice leads to a dead end, helping find all or the best solutions.

beginner

Why can't greedy algorithms solve all problems?

Greedy algorithms make the best local choice at each step but may miss the best overall solution because they don't reconsider earlier choices.

intermediate

Give an example problem where greedy fails but backtracking works.

The "Subset Sum" problem: Greedy might pick large numbers first and miss a valid subset, but backtracking tries all combinations to find the correct subset.

intermediate

How does backtracking explore the solution space?

Backtracking explores by building solutions incrementally and abandoning paths that cannot lead to a valid solution, effectively pruning the search space.

intermediate

What is a key sign that a problem might need backtracking instead of greedy?

If the problem requires checking many combinations or the best global solution depends on future choices, greedy likely fails and backtracking is needed.

Which approach tries all possible solutions and backtracks when stuck?

A Backtracking

B Greedy

C Divide and Conquer

D Dynamic Programming

Backtracking explores all options and undoes choices when they don't work.

Why might a greedy algorithm fail to find the best solution?

A It uses recursion.

B It tries all combinations.

C It only looks at local best choices, not the whole problem.

D It sorts the input first.

Greedy algorithms pick the best immediate option, which may not lead to the best overall solution.

Which problem is a classic example where greedy fails but backtracking works?

A Binary Search

B Subset Sum

C Merge Sort

D Breadth-First Search

Subset Sum requires checking combinations, which greedy can't handle correctly.

What does backtracking do when it finds a dead end?

A It goes back and tries a different path.

B It stops immediately.

C It picks the next best local choice.

D It sorts the data.

Backtracking undoes the last choice and tries alternatives.

Which is a sign that backtracking might be needed?

A The problem is linear.

B The problem is sorted.

C The problem has only one solution.

D The problem needs checking many combinations.

Backtracking is useful when many combinations must be explored.

Explain why greedy algorithms can fail and how backtracking solves those cases.

Think about local vs global decisions and exploring all possibilities.

Describe a real-life example where backtracking is better than greedy.

Imagine picking items to fit a bag exactly.