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 local choice at each step but may miss the best overall solution because they don't reconsider past choices.

intermediate

Give an example problem where greedy fails but backtracking works.

The classic example is the "Subset Sum" problem: greedy may pick large numbers first and miss a valid subset, but backtracking tries all subsets to find the correct answer.

intermediate

How does backtracking ensure finding all solutions?

Backtracking explores every possible path by making a choice, moving forward, and undoing the choice if it leads to no solution, thus covering all options.

beginner

What is a key difference between greedy and backtracking approaches?

Greedy makes one pass with local best choices and no backtracking, while backtracking tries all possibilities and backtracks when stuck.

Which approach tries all possible solutions by undoing choices when needed?

A Dynamic Programming

B Greedy

C Divide and Conquer

D Backtracking

Backtracking explores all options and backtracks when a path fails.

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

A It sorts the input first

B It only considers local best choices, ignoring future consequences

C It uses recursion

D It tries all possibilities

Greedy algorithms pick the best immediate option without looking ahead.

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

A Subset Sum

B Binary Search

C Merge Sort

D Fibonacci Sequence

Subset Sum requires exploring all subsets, which greedy cannot do correctly.

What does backtracking do when it reaches a dead end?

A Return the current solution

B Stop immediately

C Undo the last choice and try another

D Sort the data

Backtracking reverses the last step to explore other options.

Which approach is best when you need to find all possible solutions?

A Backtracking

B Greedy

C Binary Search

D Heap Sort

Backtracking explores all solution paths, unlike greedy.

Explain why greedy algorithms cannot solve all problems and how backtracking overcomes this limitation.

Think about how each approach chooses steps and handles mistakes.

Describe a real-life situation where backtracking is useful but greedy fails.

Imagine choosing items or paths where early choices affect final success.

Practice

1. Why is backtracking preferred over greedy algorithms in problems like the N-Queens puzzle?

easy

A. Because backtracking uses less memory than greedy algorithms

B. Because greedy algorithms always find the optimal solution quickly

C. Because backtracking explores all possible solutions and can backtrack on wrong choices

D. Because greedy algorithms do not use recursion

Solution

1. Step 1: Understand problem requirements

   The N-Queens puzzle requires placing queens so none attack each other, needing exploration of many possibilities.

2. Step 2: Compare algorithm approaches

   Backtracking tries all options and reverses wrong choices, while greedy picks immediate best without reconsidering.

3. Final Answer:

   Because backtracking explores all possible solutions and can backtrack on wrong choices -> Option C

4. Quick Check:

   Backtracking explores all options = A [OK]

Hint: Backtracking tries all paths; greedy picks immediate best [OK]

Common Mistakes:

• Thinking greedy always finds the best solution
• Confusing memory usage between algorithms
• Assuming backtracking is always slower

2. Which of the following is the correct syntax to start a backtracking function in C++ for solving a subset sum problem?

easy

A. int backtrack(vector<int> nums, int sum) { }

B. void backtrack(int index, int currentSum, vector<int>& nums) { }

C. void backtrack(int sum, int index) { }

D. bool backtrack(int currentSum, vector<int> nums) { }

Solution

1. Step 1: Identify typical backtracking parameters

   Backtracking usually tracks current index, current sum, and the input list by reference for efficiency.

2. Step 2: Check each option's parameter order and types

   void backtrack(int index, int currentSum, vector<int>& nums) { } correctly uses index, currentSum, and reference to vector; others have wrong order or pass by value unnecessarily.

3. Final Answer:

   void backtrack(int index, int currentSum, vector<int>& nums) { } -> Option B

4. Quick Check:

   Correct parameter order and reference = B [OK]

Hint: Backtracking needs index, current state, and reference input [OK]

Common Mistakes:

• Passing vector by value causing inefficiency
• Wrong parameter order
• Using incorrect return type for backtracking

3. What will be the output of the following C++ code snippet that uses backtracking to print all subsets of {1, 2}?

void backtrack(int i, vector<int>& nums, vector<int>& subset) {
    if (i == nums.size()) {
        for (int x : subset) cout << x << " ";
        cout << "| ";
        return;
    }
    subset.push_back(nums[i]);
    backtrack(i + 1, nums, subset);
    subset.pop_back();
    backtrack(i + 1, nums, subset);
}

int main() {
    vector<int> nums = {1, 2};
    vector<int> subset;
    backtrack(0, nums, subset);
    return 0;
}

medium

A. 1 2 | 1 | 2 | |

B. 1 2 | 2 | 1 | |

C. 1 2 | 1 | | 2 |

D. | 1 | 2 | 1 2 |

Solution

1. Step 1: Trace recursive calls with subset additions

   First call adds 1 and 2, prints "1 2 | ". Then backtracks to remove 2, prints "1 | ". Then removes 1, adds 2, prints "2 | ". Finally prints empty subset "| ".

2. Step 2: Confirm output order matches 1 2 | 1 | 2 | |

   Output order is "1 2 | 1 | 2 | | ", matching 1 2 | 1 | 2 | | exactly.

3. Final Answer:

   1 2 | 1 | 2 | | -> Option A

4. Quick Check:

   All subsets printed in order = D [OK]

Hint: Backtracking prints subsets by including/excluding elements [OK]

Common Mistakes:

• Mixing order of subset outputs
• Forgetting to pop elements after recursion
• Confusing subset print format

4. Identify the bug in this backtracking code snippet for generating permutations of {1, 2}:

void permute(vector<int>& nums, int start) {
    if (start == nums.size()) {
        for (int x : nums) cout << x << " ";
        cout << "\n";
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        permute(nums, start + 1);
    }
}

medium

A. Loop should start from 0 instead of start

B. Incorrect base case condition

C. Function should return int instead of void

D. Missing swap(nums[start], nums[i]) to revert after recursion

Solution

1. Step 1: Analyze swap usage in recursion

   Swapping elements before recursion changes order, but must be reverted after to restore original state.

2. Step 2: Identify missing revert swap

   Code swaps but never swaps back after recursive call, causing incorrect permutations.

3. Final Answer:

   Missing swap(nums[start], nums[i]) to revert after recursion -> Option D

4. Quick Check:

   Swap must be reverted after recursion = C [OK]

Hint: Always revert swaps after recursive calls in permutations [OK]

Common Mistakes:

• Not swapping back after recursion
• Wrong base case check
• Incorrect loop range

5. Given the coin denominations {1, 3, 4} and a target sum 6, why does a greedy algorithm fail to find the minimum number of coins, and how does backtracking solve it?

hard

A. Greedy picks largest coin first (4), then 1+1, total 3 coins; backtracking tries all combos and finds 2 coins (3+3)

B. Greedy always finds minimum coins; backtracking is slower but same result

C. Greedy picks smallest coins first; backtracking picks largest coins first

D. Greedy and backtracking both fail for this input

Solution

1. Step 1: Understand greedy approach on coin change

   Greedy picks largest coin <= target repeatedly: picks 4, then two 1s, total 3 coins.

2. Step 2: Understand backtracking approach

   Backtracking tries all combinations, finds 3+3 = 6 with 2 coins, which is fewer than greedy's 3 coins.

3. Final Answer:

   Greedy picks largest coin first (4), then 1+1, total 3 coins; backtracking tries all combos and finds 2 coins (3+3) -> Option A

4. Quick Check:

   Greedy fails minimum coins; backtracking finds optimal = A [OK]

Hint: Greedy may miss combos; backtracking tries all [OK]

Common Mistakes:

• Assuming greedy always optimal
• Confusing coin picking order
• Ignoring backtracking's exhaustive search