Why Backtracking and What Greedy Cannot Solve in DSA C++ - Why It Works

Concept Flow - Why Backtracking and What Greedy Cannot Solve

Start Problem

↓

Try Greedy Choice

↓

Is Greedy Choice Optimal?

No→Backtrack & Try Other Choices

↓

Explore Next Possibility

↓

Accept Choice

↓

All Choices Explored?

No→Backtrack

↓

Solution Found

↓

End

The flow shows greedy tries a quick choice, but if it fails, backtracking explores all options by trying and undoing choices until the best solution is found.

Execution Sample

DSA C++

bool backtrack(int step) {
  if (step == n) return true;
  for (int choice : choices) {
    if (valid(choice)) {
      make(choice);
      if (backtrack(step+1)) return true;
      undo(choice);
    }
  }
  return false;
}

This code tries all choices at each step, backtracks if a choice leads to no solution, unlike greedy which picks one choice quickly.

Execution Table

Step	Operation	Current Step	Choice Tried	Action	Backtrack?	Visual State
1	Try Greedy Choice	0	Choice A	Make Choice A	No	A
2	Recurse Next Step	1	Choice B	Make Choice B	No	A -> B
3	Recurse Next Step	2	Choice C	Make Choice C	No	A -> B -> C
4	Check Solution	3	-	No Solution	Yes	A -> B -> C
5	Backtrack	3	Choice C	Undo Choice C	Yes	A -> B
6	Try Next Choice	2	Choice D	Make Choice D	No	A -> B -> D
7	Check Solution	3	-	No Solution	Yes	A -> B -> D
8	Backtrack	3	Choice D	Undo Choice D	Yes	A -> B
9	Backtrack	2	Choice B	Undo Choice B	Yes	A
10	Try Next Choice	1	Choice E	Make Choice E	No	A -> E
11	Check Solution	2	-	No Solution	Yes	A -> E
12	Backtrack	2	Choice E	Undo Choice E	Yes	A
13	Backtrack	1	Choice A	Undo Choice A	Yes
14	Try Next Choice	0	Choice F	Make Choice F	No	F
15	Check Solution	1	-	Solution Found	No	F (Complete)
16	End	-	-	-	-	Solution: F

💡 All choices tried with backtracking until a valid complete solution is found at step 15.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	Final
step	0	1	2	3	3	2	3
choice	-	A	B	C	C	D	F
visual_state	""	A	A -> B	A -> B -> C	A -> B -> C	A -> B	F

Key Moments - 3 Insights

Why does the algorithm undo a choice after trying it?

Because if the choice does not lead to a solution, we must remove it to try other choices, as shown in rows 5, 8, 9, and 12 where undo happens before trying new options.

Why can't greedy alone solve this problem?

Greedy picks the first best choice without checking all options, which can miss solutions. The table shows greedy choice A leads to dead ends, so backtracking tries other choices like F to find a solution.

What does 'Backtrack?' column mean in the execution table?

It shows when the algorithm reverses a previous choice to explore other possibilities, crucial for exploring all options, as seen in steps 5, 8, 9, and 12.

Visual Quiz - 3 Questions

Look at the execution table, what is the visual state after step 3?

A A -> B -> D

B A -> B

C A -> B -> C

D F

💡 Hint

Check the 'Visual State' column at step 3 in the execution table.

At which step does the algorithm first backtrack?

A Step 5

B Step 4

C Step 6

D Step 9

💡 Hint

Look for the first 'Yes' in the 'Backtrack?' column in the execution table.

If greedy choice A was always correct, what would happen to the backtracking steps?

A More backtracking steps would occur

B Backtracking steps would be skipped

C Backtracking would happen only at the end

D Backtracking would happen before any choice

💡 Hint

Refer to the execution table rows where backtracking occurs after greedy choice A fails.

Concept Snapshot

Backtracking tries all choices step-by-step, undoing wrong ones to find solutions.
Greedy picks the best immediate choice but can miss solutions.
Backtracking explores all possibilities; greedy does not.
Use backtracking when greedy fails to guarantee correct results.
Typical backtracking uses recursion and undo steps.
Backtracking is slower but complete; greedy is faster but may be wrong.

Full Transcript

Backtracking is a method to solve problems by trying all possible choices one by one. If a choice leads to a dead end, it undoes that choice and tries another. Greedy algorithms pick the best immediate choice without checking all options, which can miss the correct solution. The example code shows backtracking trying choices recursively, undoing them if they fail. The execution table traces each step, showing when choices are made, undone, and when backtracking happens. This helps understand why backtracking is needed when greedy cannot solve the problem. Key moments explain why undoing is necessary and why greedy alone is insufficient. The quiz tests understanding of the execution steps and backtracking behavior.

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