Why Backtracking and What Greedy Cannot Solve in DSA C - 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, ensuring all solutions are explored.

beginner

Why can't greedy algorithms solve all problems?

Greedy algorithms make the best choice at each step without looking ahead, which can miss the overall best solution in problems needing global decisions.

intermediate

Give an example of a 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 subsets to find the correct answer.

intermediate

How does backtracking ensure correctness?

By exploring all possible choices and undoing wrong paths, backtracking guarantees finding all valid solutions or the best one if it exists.

beginner

What is a key drawback of backtracking compared to greedy?

Backtracking can be slow because it tries many possibilities, while greedy is faster but may not always find the best solution.

Which approach tries all possible options and backtracks on failure?

A Divide and Conquer

B Backtracking

C Greedy

D Dynamic Programming

Backtracking explores all options and undoes choices when they lead to dead ends.

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

A It tries all possibilities

B It stores all solutions

C It uses recursion

D It only looks at the current step

Greedy algorithms make decisions based only on the current step without considering future consequences.

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

A Sorting numbers

B Binary Search

C Subset Sum

D Finding maximum

Subset Sum requires checking combinations, which greedy cannot do correctly.

What is a main disadvantage of backtracking?

A It is slow due to many possibilities

B It is always incorrect

C It never finds a solution

D It uses no recursion

Backtracking can be slow because it explores many possible paths.

Which algorithm type is best when you need the absolute best solution and can afford more time?

A Backtracking

B Greedy

C Heuristic

D Sorting

Backtracking tries all options to find the best solution, though it may be slower.

Explain why greedy algorithms cannot solve all problems and how backtracking helps.

Think about choosing step-by-step vs exploring all paths.

Describe a scenario or problem where backtracking is necessary instead of greedy.

Consider problems where partial choices affect future options.